Don’t write a code. For part b) use Dynamic Programming to solve the question. Q

Question

Don’t write a code.
For part b) use Dynamic Programming to solve the question. Q2) 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 ["I","have", "Sam", "am", "this", "dog" String "IamSam" Output: "I am Sam" String "iadog" 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 ["I", "KU", "study", "CpE", "in'"] 1t string input: "IstudyCpEinKU" nd string input: "IstudyEEinKU" c) What is the running time of your algorithm? Note: your solution must not run in exponential time.

Explanation / 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;i++)

{

if(solve[i] == false && dictonary_has(substr[0..i]) )

solve[i] = true;

if(solve[i] == true)

{

if(i==n)

return true;

for(int j = i+1; j<=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 D
• Subjects

---

---

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