Start learning free

LESSON 450 OF 536 · DYNAMIC PROGRAMMING

Word Break in Java: Dynamic Programming in O(n · m · k)

Practice O(n · m · k) Read the full explanation

You are given a string s and an array 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 HashSet 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

    JAVA · DYNAMIC PROGRAMMING

    Word Break in Java, explained

    Problem overview

    The method wordBreak receives a string s and an array of strings wordDict. It returns true when s can be written as one or more dictionary words placed one after another with nothing left over, and false otherwise. A word can be used as many times as needed.

    With s = "leetcode" and wordDict = ["leet", "code"] the answer is true: the string is "leet" followed by "code". With s = "applepenapple" and ["apple", "pen"] it is also true, and "apple" is used twice. With s = "catsandog" and ["cats", "dog", "sand", "and", "cat"] it is false: a split can start with "cat" and "sand" or with "cats" and "and", and both leave "og", which is not a word.

    The statement asks for O(n · m · k) time and O(n) extra space, where n is the length of s, m the number of words and k the length of the longest word.

    Approach: solve every prefix once

    The direct idea is to try every way of cutting the string. That explodes quickly. With s = "aaaaaaab" and the words "a", "aa" and "aaa", the number of ways to cut the a's grows exponentially, and none of them works because of the final "b". A plain recursion repeats the same sub-questions over and over.

    The fix is to answer a smaller question once and remember it. Let dp[i] be true when the first i characters of s can be split into words. The empty prefix needs no words, so dp[0] is true. The answer to the whole problem is dp[n].

    To decide dp[i], look at the last word of a split. The first i characters can be split exactly when some dictionary word w ends them and the part before w can be split too. If w has L characters, three things must hold: L <= i so the word fits, the characters from index i - L up to i - 1 spell w, and dp[i - L] is true. One word that satisfies all three is enough.

    Since dp[i] only needs entries for shorter prefixes, filling the table from left to right guarantees that everything it reads is already known. For "catsandog" the finished table, from dp[0] to dp[9], is:

    [true, false, false, true, true, false, false, true, false, false]

    dp[3] ("cat"), dp[4] ("cats") and dp[7] ("catsand", as "cat" + "sand" or "cats" + "and") are true, but dp[9] is false, so the method returns false.

    Step by step

    1. Store the length of s in an int named n. The table has an entry for every prefix length from 0 to n, so this number is used repeatedly.
    2. Create dp as new boolean[n + 1]. A new boolean array is all false, which is what we want: a prefix counts as splittable only once a split has been found for it.
    3. Set dp[0] to true. Every split starts from the empty prefix, so the first word of a split depends on this entry.
    4. Loop i from 1 to n inclusive. The last length, n, is the whole string, so the condition is i <= n.
    5. Loop over the words with an enhanced for. Each word is a candidate for the last word of a split of the first i characters.
    6. Compute start, the index where the word would begin if it ended the prefix: i - word.length(). It is negative when the word is longer than the prefix.
    7. Check the three conditions in one if, joined by &&: the word fits (start >= 0), the part before it is splittable (dp[start]) and the text really ends with the word (s.substring(start, i).equals(word)). The order matters, as explained below.
    8. Set dp[i] to true inside the if.
    9. Return dp[n] after the outer loop.

    The solution in Java

    class Solution {
    public boolean wordBreak(String s, String[] wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (String word : wordDict) {
                int start = i - word.length();
                if (start >= 0 && dp[start] && s.substring(start, i).equals(word)) {
                    dp[i] = true;
                }
            }
        }
        return dp[n];
    }
}

    The Java details worth a closer look:

    • Short-circuit &&. Java stops at the first false operand. When start is negative, dp[start] is never evaluated, so there is no ArrayIndexOutOfBoundsException. The substring is also built only when the part before it is splittable, which saves work.
    • substring(start, i) takes the characters from index start up to, but not including, index i. The prefix of length i ends at index i - 1, so this is exactly the stretch of text the word must match.
    • Compare strings with equals. The operator == checks whether two references point to the same object. For String p = new String("pen"), the expression p == "pen" is false while p.equals("pen") is true. A substring is a new object, so == would reject matches.
    • Array defaults. new boolean[n + 1] fills every slot with false, and that is why only dp[0] needs to be set by hand.
    • The table is size n + 1. Index n is valid because the array has one more slot than the string has characters.

    Complexity

    The table has n + 1 entries. For each one the loop tries all m words, and comparing a word with the end of the prefix takes up to k character comparisons, where k is the length of the longest word. That gives O(n · m · k) time. The table takes O(n) extra space.

    If the dictionary is large, a different version puts the words in a HashSet and, for each i, looks up only the pieces of length 1 to k that end at i. This lesson keeps the simpler loop over the array.

    Edge cases and common mistakes

    • A word longer than the prefix. Without the start >= 0 check, dp[start] and substring are called with a negative index and the method throws.
    • Checking only a prefix match. Matching a word at the start of the remaining text greedily fails on "catsandog"-style inputs, where taking "cat" first or "cats" first leads to different results. The table tries every word at every position.
    • Forgetting dp[0] = true. Every entry would stay false, because no split would have a starting point.
    • Using == on strings, as above.
    • Reusing a word. The same word may be used again, which the loop allows because every word is tried again for every i.

    Testing

    These inputs and results come from running the solution:

    swordDictResult
    "leetcode"["leet", "code"]true
    "applepenapple"["apple", "pen"]true
    "catsandog"["cats", "dog", "sand", "and", "cat"]false
    "aaaaaaab"["a", "aa", "aaa"]false
    "abab"["ab"]true
    "a"["b"]false
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free