Start learning free

LESSON 471 OF 569 · DYNAMIC PROGRAMMING

Word Break

Practice O(n · m · k)

You are given a string s and a list of strings wordDict, the dictionary. Return True if s can be split into one or more dictionary words, written one after another with nothing left over, or False otherwise.

The same dictionary word may be used any number of times in a split.

 

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: True
Explanation: "leetcode" is "leet" followed by "code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: True
Explanation: "applepenapple" is "apple" + "pen" + "apple". The word "apple" is used twice.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: False
Explanation: A split can start with "cat" + "sand" or with "cats" + "and". Both leave "og",
which is not a word and doesn't start with one.

 

Constraints:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and every wordDict[i] are made of lowercase English letters only, a to z.
  • All the words of wordDict are distinct.

Note:

Your algorithm should run in O(n · m · k) time and use O(n) extra space, where n is the length of s, m the number of words in wordDict and k the length of the longest word.



Trying every way to cut s is far too slow: with s = "aaa…ab" and the words "a", "aa", "aaa"…, the number of ways to cut the a's grows exponentially, and none of them works. Solve smaller versions of the problem instead: let dp[i] be True when the first i characters of s can be split into words. dp[0] is True: the empty prefix needs no words at all. The answer is dp[n].

Fill dp from left to right. The first i characters can be split exactly when they end with some word w and the part before that word can be split. If w has L characters, it must fit (L <= i), the L characters that end the prefix, from position i - L on, must spell w, and dp[i - L] must be True. Try every word for every i: one that works is enough.

The table has n + 1 entries. Each one tries the m words, and comparing a word with the end of the prefix takes up to k character comparisons: O(n · m · k) time. The table takes O(n) space.
When the dictionary is large, you can put the words in a set instead and, for each i, look up only the pieces of length 1 to k that end at i.
STEP 1 OF 9
    Ctrl + Enter to check