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
How does the structure of shakespeare's sonnets affect the content of the poem?
Natalka [10]
The correct answer is D. There is a change in mood from the quatrains to the final couplet. This is common in the English sonnet that the final couplet is used to change the mood and add new meaning to what was previously said, thus being a sort of a peak for the sonnet. 
5 0
3 years ago
Read 2 more answers
Everyone help me with that):)
katen-ka-za [31]

Answer:

1) went

2) was

3. saw

4.performed

5.came

6.were

7.cried

8.said

9.thought

10. did

4 0
2 years ago
What figure of speech is at the center of Emily Dickinson’s “’Hope’ is the thing with feathers”?
Klio2033 [76]
Not 100% sure but this is my opinion B). Metaphor =============================== HOPE THIS HELPS!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
6 0
3 years ago
"Kin" by Carl Sandburg
goldfiish [28.3K]
A metaphor, because it is a comparison without like or as
6 0
2 years ago
Read 2 more answers
The book prompted the federal government to review it's policy on pesticide use, and the use of DDT was banned. Choose the best
Vilka [71]

Answer: D - Its

Explanation: The sentence says "review it's policy." However, "it's" with and apostrophe always means its a contraction (it is) so this sentence is not grammatically correct. Replacing "it's" with "its" (the possessive form meaning "it" owns the "policy") would correct the error.

4 0
2 years ago
Other questions:
  • Which of the following are necessary to critical listening? Select all that apply.
    12·2 answers
  • Which is an example of alliteration? I sit and look workings of battle I see these sights
    12·1 answer
  • A driver's license, togrther with a bank card, ___ required for identification
    13·2 answers
  • Help me for 35 points please &lt;3
    14·1 answer
  • Which of the following rules did Joan's break
    8·2 answers
  • Can anyone tell me what is occupation​
    7·1 answer
  • It's hard to beat a boiled egg for breakfest what does beat mean in the sentence
    7·2 answers
  • What is a thesis statement?
    9·1 answer
  • PLEASE HELP Read the excerpt from Martin Luther King Jr.’s "The American Dream” speech.
    9·2 answers
  • What would you expect to see on the set for a scene in a play that takes place in a middle school classroom
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!