Start learning free

LESSON 454 OF 540 · DYNAMIC PROGRAMMING

Word Break in Scala: Dynamic Programming Over Prefixes

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 mutable.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

    SCALA · DYNAMIC PROGRAMMING

    Word Break in Scala, explained

    Problem overview

    The method wordBreak(s: String, wordDict: Array[String]): Boolean answers one question: can s be cut into pieces that are all words of wordDict, written one after another with nothing left over? A word may be used as many times as you like.

    With s = "leetcode" and wordDict = Array("leet", "code") the answer is true, because the string is "leet" followed by "code". With "applepenapple" and Array("apple", "pen") it is also true: "apple" is used twice. With "catsandog" and Array("cats", "dog", "sand", "and", "cat") it is false. Both ways to start, "cat" + "sand" and "cats" + "and", leave "og", which is not a word and does not start with one.

    Approach: answer the question for every prefix

    Trying every way to cut the string is too slow. With s = "aaaaaaaab" and the words "a", "aa" and "aaa", the number of ways to cut the a's grows exponentially, and every one of them fails at the final b.

    A greedy rule such as "always take the longest word that fits" is not safe either. For s = "abcd" and the words "ab", "abc" and "cd", the longest word at the start is "abc", which leaves "d" and gets stuck. The correct split is "ab" + "cd", so the answer is true.

    The lesson solves smaller versions of the problem instead. 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, and the answer is dp(n) for a string of length n.

    Now fill the table from left to right. The first i characters can be split exactly when they end with some word w and what comes before that word can be split too. If w has L characters, three things must hold: L <= i (the word fits), dp(i - L) is true, and the L characters from index i - L up to i - 1 spell w. One word that works is enough.

    For "leetcode" and Array("leet", "code"), the table from dp(0) to dp(8) ends up as:

    true false false false true false false false true

    Position 4 is true because the first four characters are "leet" and dp(0) is true. Position 8 is true because the last four characters are "code" and dp(4) is true. For "catsandog" the table is:

    true false false true true false false true false false

    Prefixes of length 3, 4 and 7 can be split ("cat", "cats", "catsand"), but nothing extends to length 9, so dp(9) is false.

    Step by step

    1. Store the length of s in n. The table has an entry for every prefix length from 0 to n, so the length is needed in several places.
    2. Create dp as an Array[Boolean] of n + 1 entries. A new Boolean array starts with every entry false, which is the right default: a prefix counts as splittable only after a split is found.
    3. Set dp(0) to true. Every split starts from the empty prefix.
    4. Loop over the prefix lengths with i <- 1 to n. to includes its end, so the whole string is the last case, and each entry only needs shorter prefixes, which are finished by then.
    5. Loop over the words. Each word is tried as 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 three conditions joined by &&: start >= 0, dp(start), and s.substring(start, i) == word. The checks run left to right and stop at the first false one, so dp(start) is never read with a negative index, and the text is compared only when the part before it already splits.
    8. Mark dp(i) as true inside the if.
    9. Return dp(n) as the last expression of the method.

    The solution in Scala

    class Solution {
    def wordBreak(s: String, wordDict: Array[String]): Boolean = {
        val n = s.length
        val dp = new Array[Boolean](n + 1)
        dp(0) = true
        for (i <- 1 to n) {
            for (word <- wordDict) {
                val start = i - word.length
                if (start >= 0 && dp(start) && s.substring(start, i) == word) {
                    dp(i) = true
                }
            }
        }
        dp(n)
    }
}

    The Scala details worth a closer look:

    • Parentheses index arrays. Scala writes dp(i), not dp[i], for reading and dp(i) = true for writing. Both are method calls on the array.
    • 1 to n includes n. 0 until n would stop one short and never fill dp(n), the entry the method returns.
    • substring(start, i) excludes its end index. It holds the characters from start up to i - 1, exactly word.length of them.
    • == compares strings by content in Scala, so it works directly for the words.
    • The last expression is the result. dp(n) has no return in front of it. The for loops produce no value of their own, so they sit before it as statements.

    The substring check is the only place that looks at characters. A version that skipped the dp(start) test would still be correct, only slower, because it would compare text for splits that can never work. Putting dp(start) before the comparison avoids most of those comparisons.

    Complexity

    Time: O(n · m · k). 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, where k is the length of the longest word.

    Space: O(n). The table is the only structure that grows with the input.

    When the dictionary is large, there is a variant that puts the words in a set and, for each i, looks up only the pieces of length 1 up to the longest word's length that end at i. It gives the same answers: on the eight inputs listed under Testing, in order, it returns true true false true false false false true.

    Edge cases and common mistakes

    • A word longer than the string. s = "ab" with Array("abc") gives false. The start >= 0 check is what keeps substring from being called with a negative start. Calling "leetcode".substring(-1, 2) throws a StringIndexOutOfBoundsException.
    • Reading dp before checking start. With start = -1, dp(start) throws an ArrayIndexOutOfBoundsException. The order of the && conditions matters.
    • Forgetting dp(0) = true. Nothing could ever become true, so every answer would be false.
    • Taking the longest word first. The "abcd" example above shows a greedy split that gives false where the right answer is true.
    • Stopping at the first word that fits. The words that fit at a position are only candidates. Each one is a different way to continue, and the table keeps all of them.
    • Returning dp(n - 1). The entry for the whole string is dp(n), because dp(i) counts characters, not indexes.

    Testing

    • "leetcode" with Array("leet", "code") gives true.
    • "applepenapple" with Array("apple", "pen") gives true.
    • "catsandog" with Array("cats", "dog", "sand", "and", "cat") gives false.
    • "abcd" with Array("ab", "abc", "cd") gives true.
    • "a" with Array("b") gives false.
    • "ab" with Array("abc") gives false.
    • "aaaaaaaab" with Array("a", "aa", "aaa") gives false.
    • "aaaa" with Array("a", "aa") gives true.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free