An American spy is deep undercover in the hostile country of Phonemia. In order

Question

An American spy is deep undercover in the hostile country of Phonemia. In order to not to waste scarce resources...

The idea is to use a dynamic programming approach I guess. Any ideas would be great.

A-12.3 An American spy is deep undercover in the hostile country of Phonemia. In order not to waste scarce resources, any time he wants to send a message back home, he removes all the punctuation from his message and converts all the letters to uppercase. So, for example, to send the message, "Abort the plan! Meet at thel Dark Cabin." he would transmit ABORTTHEPLANMEETATTHEDARKCABIN Given such a string, S, of n uppercase letters, describe an efficient way of break ing it into a sequence of valid English words. You may assume that you have www.it-ebooks.info Chapter 12. Dynamic Programming a function, valid(s), which can take a character string, s, and return true if and only if s is a valid English word. What is the running time of your algorithm, assuming each call to the function, valid, runs in O(1) time?

Explanation / Answer

The most efficient was of breaking the input into a sequence of English words would be using Dynamic programming. The method is described below:

There would be two loops involved, one of i and an inner loop of j. The total running time would be O(n^2) because we use O(1) about n^2 times to check if dp[ i ] is true.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.