1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
miskamm [114]
2 years ago
8

Given a non-empty string s and a dictionary containing a list of unique words, design a dynamic programming algorithm to determi

ne 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

English
1 answer:
nlexa [21]2 years ago
8 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<i<k and s(i+1),kis a word in the dictionary
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.

You might be interested in
Discussion Topic
kakasveta [241]

Answer:

Poetry is special because the author uses a different form of wording to express themselves. Whether it's with rhyming or simply just putting their thoughts on stanzas, poetry is different from other forms of writing in many ways.

Explanation:

5 0
3 years ago
Anna is telling Joy all about Maya’s recent engagement. Because they share __________, Anna assumes that Joy knows a little abou
Vlada [557]

Answer:

are there any answer choices?

Explanation:

5 0
3 years ago
What is good word choice for the hobbit?
kotegsom [21]
A good word choice i would guess that it would be small and a hermet because they love living alone in their cottages
8 0
3 years ago
Read 2 more answers
How can predicting plot and summarizing themes aid in understanding a short story?
erica [24]

Paragraph:

By analyzing the plot and understanding how it contributes to the general mood and understanding of a short story, we can see how the author utilizes inferences and what they may be foreshadowing in the future of our book.

8 0
2 years ago
The season ends in June. What is the verb tense
VMariaS [17]

Answer:

end

Explanation:

because it's something you do like an action

for example: I end my workout.

6 0
3 years ago
Other questions:
  • What 5 letter word can be spell with babek?
    11·1 answer
  • Which detail provides the most cultural context for this excerpt about the Cold War? There was also a sense of urgency. The Pent
    7·2 answers
  • How does the oxymoron "burning cold" affect the meaning of this sentence?
    14·1 answer
  • PLEASE HELP!!!! HAVE TO FINISH TO GET MY COURSE DONE!!!!
    9·1 answer
  • Why are reading and writing necessary in today’s world
    9·1 answer
  • Select the correct answer. Which statement would best conclude the following passage? Earth Hour is an annual event when people
    12·1 answer
  • Actions that strained the relationship between American Indians and Europeans:
    13·1 answer
  • Will give Brainiest to whoever helps me :)
    14·2 answers
  • Make a sentece that shows an understanding of the situation and needs of others.
    11·1 answer
  • John Proctor the Crucible <br> When does he say he sees himself as a sinner?
    12·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!