2) Given a string of characters without any spaces between them and a dictionary

Question

2) Given a string of characters without any spaces between them and a dictionary of valid English words, find all possible ways to break the string in individual dictionary words. Examples: dictionary- "have", "Sam", "am", "this", "dog"] String "lamSam Output: "I am Sam" String ="thisisadog" Output: String can't be broken a) Design the recursive sub-problem condition(s) Use your solution in (a) to solve the following problems: You have to show the complete solution of the DP steps either by top down or bottom-up approach. b) dictionary-T "KU", "study", "CpE", "in"] string input: "IstudyCpEinKU" 2nd string input: "IstudyEEinkU" cWhat is the running time of your algorithm? Note: your solution must not run in exponential time

Explanation / Answer

Answer:

A) This problem can be solved with the help of following DP.

Given a string S, let it's length is n, then we create a matrix solve[n] which is initialised to false.

solve[i] is true if the string S[0...i] can be segmented into dictonary words.

I am giving the sudo code to solve this problem.

for(int i = 0;i< n; j++)

{

//Updating solve[j] if it is false and can be made true with help of other words

if(solve[j] == false && dictonary_has(s[i...j-1])

solve[j] = true;

if(j == n && solve[j] == true)

return true

}

}

C) Complexity of the above model is O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.