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
What is the rival gang of the sharks in west side story??
pantera1 [17]
West Side Story is the honor winning adjustment of the great sentimental disaster, "Romeo and Juliet". The quarreling families end up noticeably two warring New York City posses the white Jets driven by Riff and the Puerto Rican Sharks, driven by Bernardo.
7 0
3 years ago
Add quotation marks where they need to go! Tysm!! Answer only if you know
denis23 [38]
“i would like to do that again”
4 0
3 years ago
Which quotation from Roosevelt’s request for a declaration of war is an example of a hasty generalization?
user100 [1]

Answer:

"We will gain the inevitable triumph." is the correct answer.

Explanation:

3 0
3 years ago
50PTS Anne Frank CHARACTER TRAITS CHART: Give at least three examples per character per column. Please spread your entries out o
Charra [1.4K]

Answer:

Anne:  is a lively, curious girl of thirteen at the beginning of the play. She remains optimistic throughout the months they are in hiding and always makes the best of the situation she is in.

Mr. van Daan: is intelligent, opinionated, pragmatic, and somewhat egotistical. He is temperamental, speaks his mind openly, and is not afraid to cause friction, especially with his wife, with whom he fights frequently and openly.

Mr. Dussel  particularly difficult to deal with because he shares a room with her, and she suffers the brunt of his odd personal hygiene habits, pedantic lectures, and controlling tendencies.

4 0
3 years ago
Excellent dialogue makes it a priority to _________, rather than to __________.
valkas [14]

Answer:

show, tell

Explanation:

:)

5 0
3 years ago
Other questions:
  • "..and tears stood on the rims of his red eyes." Is this personification, alliteration, or both?
    15·1 answer
  • If you still cannot uncover the meaning of symbols , what is the last thing you should do? A. do some research on the topic B. G
    7·2 answers
  • In the Necklace, Why doesn’t the women like to visit her old friend, the school mate that she met at the convent?
    14·1 answer
  • During the Great Indian Debate, what topics did the characters debate?
    11·1 answer
  • An idea that's intended to make the reader take notice and want to read on is called a
    8·2 answers
  • 5.
    11·1 answer
  • 10. Which of the following quotes should be used to fill in Missing Part A? In other words, which
    10·1 answer
  • HELP WITH EASY QUESTION
    7·2 answers
  • 4. What leads Macbeth to irrationality (behave irrationally)?
    11·1 answer
  • 4. What important feature is missing from an animated "crankie" script?
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!