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]
3 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]3 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
Allusions can help reveal a person’s importance. narration. perspective. appearance.
AleksAgata [21]

Answer:

perspective

Explanation:

Allusions is an indirect reference to a person , place or event that allows the writer to make a point without describing everything about a person , place or event. It's just a passing remark, intended to be understood by the reader since it's supposed to be a well-known topic. Writers use this literary device to communicate a specific emotion to the audience or the reader.

hope this helped!

8 0
3 years ago
Is where is the airport fragment or sentence
Naily [24]
It is a fragment because it need more writing to it
4 0
3 years ago
Read 2 more answers
What have you learn about vision and disillusion by reading this excerpt from Gulliver's travels?
Setler [38]

Answer:

What excerpt tho?

Explanation:

Theres like no excerpt?

4 0
3 years ago
Read 2 more answers
Throughout the story, Winterbourne tries to
IRINA_888 [86]

<span>In the novella, _Daisy Miller_, by Henry James, there is a character by the name of Frederick Winterbourne.  Frederick Winterbourne is enthralled by Daisy Miller and spends a great deal of time thinking about her, but mainly he tries discover whether or not Daisy is a flirt by trying to discover for himself the definition of what it actually means to be a flirt.</span>






6 0
4 years ago
Read 2 more answers
Not all plants grow in the same way. some plants grow and reproduce in one year and are called annuals. some plants grow and rep
madam [21]

Answer:d

Explanation: some plants grow and reproduce in two years and are called biennials

4 0
3 years ago
Other questions:
  • If a writer were writing a modern-day story based on the Theseus myth featured in “Cruel Tribute,” what would the story’s plot m
    6·2 answers
  • Replace the bold phrase in the following sentence with more specific vocabulary.
    15·2 answers
  • Plz Help
    13·1 answer
  • Jonathan is writing a research paper on imagery in Wuthering Heights by Emily Brontë. He wants to include relevant ideas from an
    12·2 answers
  • Write an article about the discovery of a preserved body on the fourth floor of the bead and breakfast.
    11·1 answer
  • Differentiate between cash with draw for office use and cash withdrawal for personal use​
    5·2 answers
  • A supervisor, who is not yours, becomes upset with a coworker and severely criticizes the coworker in front of you. The coworker
    15·2 answers
  • What is the main topic of this excerpt?
    5·2 answers
  • 3. The people thought a lion/loin was nearby
    11·1 answer
  • Which best describes a purpose of a business letter?
    8·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!