Start learning free

LESSON 454 OF 540 · DYNAMIC PROGRAMMING

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

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

    KOTLIN · DYNAMIC PROGRAMMING

    Word Break in Kotlin, explained

    Problem overview

    You get a string s and an array of words wordDict. The function wordBreak returns true if s can be cut into pieces that are all dictionary words, with nothing left over. A word can be used as many times as you like.

    For s = "leetcode" and the words "leet" and "code" the answer is true: the string is "leet" followed by "code". For "applepenapple" with "apple" and "pen" it is also true, because "apple" is used twice. For "catsandog" with "cats", "dog", "sand", "and" and "cat" it is false: both "cat" + "sand" and "cats" + "and" leave "og", which is not a word.

    Approach

    The direct idea is to try every way to cut the string. That is far too slow. With s = "aaaaaaab" and the words "a", "aa" and "aaa", the a's can be cut in exponentially many ways, and every one of them fails at the final b. A search that explores all of them repeats the same work over and over.

    Dynamic programming removes the repetition. Let dp[i] be true when the first i characters of s can be split into words. Two facts define the table:

    • dp[0] is true. The empty prefix needs no words, and every split starts from it.
    • dp[i] is true when the prefix of length i ends with some word w and the part before that word, of length i - w.length, can be split too.

    The answer is dp[n], where n is the length of s. Each entry only needs entries for shorter prefixes, so filling the table from left to right is enough.

    Here is the table for "catsandog" from a real run. Entry 0 is the empty prefix, entry 9 the whole string:

    T F F T T F F T F F

    Entries 3, 4 and 7 are T: "cat", "cats" and "catsand" (which is "cat" + "sand" or "cats" + "and") can be split. Entry 9 is F, so the string can't. For "leetcode" the table is:

    T F F F T F F F T

    Entry 4 ("leet") is true, and entry 8 is true because it ends with "code" and entry 4 is true.

    Step by step

    1. Store the length. val n = s.length. It appears in the table size, the loop bound and the result.
    2. Create the table. BooleanArray(n + 1) has one entry per prefix length, from 0 to n. A new BooleanArray is filled with false, which is the right starting value: a prefix counts only once a split is found.
    3. Seed the empty prefix. dp[0] = true. Without it nothing could ever become true.
    4. Loop over prefix lengths. for (i in 1..n) includes n, because the whole string is the last prefix.
    5. Try each word as the last word. The inner loop for (word in wordDict) asks whether this word could end the prefix of length i.
    6. Find where the word would start. The prefix ends at index i - 1, so a word of word.length characters that ends it begins at start = i - word.length. This is negative when the word is longer than the prefix.
    7. Check three conditions. start >= 0 says the word fits. dp[start] says the part before it can be split. s.substring(start, i) == word says the prefix really ends with the word. They are joined with &&, which stops at the first false check, so dp[start] is never read with a negative index and the strings are compared only when the cheaper checks pass.
    8. Record the success. Set dp[i] = true. One working word is enough, and later words can't undo it.
    9. Return the last entry. dp[n] covers the whole string.

    The solution in Kotlin

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

    Some Kotlin details that matter here:

    • == compares contents. On strings, Kotlin's == calls equals, so it compares characters, not references. s.substring(start, i) == word is true when the two texts match, even though they are different objects.
    • substring(start, i) excludes i. It takes the characters from index start up to i - 1, exactly word.length of them. With a negative start it would throw a StringIndexOutOfBoundsException, which is why the start >= 0 check comes first.
    • 1..n includes n. Unlike 0 until n, a range written with .. has an inclusive end.
    • Arrays of strings. The dictionary is an Array<String>, and for (word in wordDict) walks over it directly.

    Complexity

    The table has n + 1 entries. Each entry tries all m words, and comparing one word with the end of the prefix takes up to k character comparisons, where k is the length of the longest word. That makes O(n · m · k) time. The table is the only extra storage, so the space is O(n). (substring also copies up to k characters, which stays within the same bound.)

    When the dictionary is large, put the words in a HashSet and, for each i, look up only the pieces of length 1 to k that end at i. That replaces the loop over every word.

    Edge cases and common mistakes

    • Forgetting dp[0] = true. Every entry stays false and the function always returns false.
    • Using 0 until n for the loop. The table would never fill entry n, and the function would return the default false.
    • Checking only that the end matches. Skipping dp[start] accepts strings where a word matches at the end but the front can't be split. For "abcd" with "abc" and "cd", the word "cd" matches the end, yet "ab" is not splittable.
    • Stopping at the first word that matches the front. A greedy choice fails when a shorter word is the right one. In "catsandog", picking "cats" or "cat" first both lead nowhere, and the table handles both at once.
    • Reading dp[start] with a negative index. Put start >= 0 first in the condition.
    • A word that never fits. A word longer than s gives a negative start for every i and is skipped.

    Testing

    Inputs worth trying, with the results the solution gives:

    • "leetcode" with "leet", "code": true
    • "applepenapple" with "apple", "pen": true
    • "catsandog" with "cats", "dog", "sand", "and", "cat": false
    • "a" with "b": false
    • "aaaaaaab" with "a", "aa", "aaa": false, quickly, because the table never repeats work
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free