Ask Question
31 March, 15:01

Given a non-empty string s and a dictionary containing a list of unique words, design a dynamic programming algorithm to determine if s can be segmented into a space-separated sequence of one or more dictionary words. if s="algorithmdesign" and your dictionary contains "algorithm" and "design". your algorithm should answer yes as s can be segmented as "algorithmdesign

+1
Answers (1)
  1. 31 March, 16:37
    0
    Let s (i), k denote the substring s (i) s (i+1) ... s k. Let Opt (k) denote whether the sub-string s1, k can be segmented using the words in the dictionary, namely (k) = 1 if the segmentation is possible and 0 otherwise. A segmentation of this sub-string s1, k is possible if only the last word (say si k) is in the dictionary theremaining substring s1, i can be segmented.

    Therefore, we have equation:Opt (k) = max Opt (i) 0
    We can begin solving the above recurrence with the initial condition that Opt (0) = 1 and then go on to comput eOpt (k) for k = 1, 2. The answer correspond-ing to Opt (n) is the solution and can be computed in Θ (n2) time.
Know the Answer?
Not Sure About the Answer?
Get an answer to your question ✅ “Given a non-empty string s and a dictionary containing a list of unique words, design a dynamic programming algorithm to determine if s can ...” in 📙 English if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers