Dynamic programming 0/49

DP fundamentals: states and transitions · 2 of 3

Choosing the state

Choose a state that holds enough to write a transition: a yes-or-no value, a prefix with a take-or-skip choice, a fixed ending position, or two values per state.

3,046 words · 14 min read

Part 1 of 7 Choosing the state

Choosing the state

In Frog 1, Climbing Stairs and Coin Change the states were easy to pick: a stone, a step, an amount of money. The value of each state was a cost or a count. The four problems in this lesson are solved the same way, by choosing states and finding a transition for each, but each one needs more thought about what a state is and what value it holds.

A table of yes and no

The first problem has a string as its input. Its states are the prefixes of the string, and each one's value is a yes or a no.

Difficulty tier:Normal

Given a string s and a list of dictionary words wordDict, return whether s can be split into a sequence of dictionary words. A word may be used more than once.

Constraints

  • 1≤1 \le s.length ≤300\le 300
  • 1≤1 \le wordDict.length ≤1000\le 1000
  • Each word has 1 to 20 lowercase letters, and the words are distinct

Sample 1 · Input

s = "leetcode", wordDict = ["leet","code"]

Output

true

Sample 2 · Input

s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

Output

false

Let ok[i] say whether the first ii characters of s can be split into dictionary words. Look at the last word of such a split. It starts at some position jj and ends just before position ii, and the jj characters in front of it must themselves split into words. So ok[i] is true when some j<ij < i has ok[j] true and the characters from position jj up to, but not including, position ii form a dictionary word.

Each jj gives one candidate, a possible value for the state from one possible last step. The frog combined its candidates with a minimum and Climbing Stairs with a sum, and here they are combined with "at least one". The base case is ok[0], which is true: an empty string needs no words.

That piece of the string is the slice s[j:i]. The listing puts the words in a set, so that testing whether a piece is a word takes one lookup.

Sign up to run
def word_break(s, words):
    words = set(words)
    ok = [True] + [False] * len(s)
    for i in range(1, len(s) + 1):
        for j in range(i):
            if ok[j] and s[j:i] in words:
                ok[i] = True
                break
    return ok[len(s)]

print(word_break("leetcode", ["leet", "code"]))
print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))

For "leetcode" the true entries are 0, 4 and 8: "leet" covers positions 0 to 4 and "code" covers 4 to 8. For "catsandog" they are 0, 3, 4 and 7, reached by "cat", by "cats", and by "cat" + "sand" or "cats" + "and". No dictionary word runs from a true entry to the end of the string, so ok[9] stays false.

For a string of nn characters the table has n+1n + 1 states, and entry ii tries up to ii values of jj. With 300 characters that is 300×301/2=45,150300 \times 301 / 2 = 45{,}150 pairs. Each test also copies the piece of the string it looks up, and in the worst case the pieces add up to about 4.5×1064.5 \times 10^6 characters, which is still fast.