Start learning free

LESSON 453 OF 539 · DYNAMIC PROGRAMMING

Word Break in C#: Dynamic Programming on 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 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

    C# · DYNAMIC PROGRAMMING

    Word Break in C#, explained

    Problem overview

    WordBreak receives a string s and an array of strings wordDict. It returns true when s can be cut into one or more dictionary words, laid one after another with nothing left over. A word may be used as many times as you like.

    For "leetcode" with {"leet", "code"} the answer is true. For "applepenapple" with {"apple", "pen"} it is also true, and "apple" is used twice. For "catsandog" with {"cats", "dog", "sand", "and", "cat"} it is false: both "cat" + "sand" and "cats" + "and" leave "og", which is not a word.

    Approach: solve every prefix

    The direct idea is to try every way to cut the string. That is exponential. With s made of many as followed by a b, and the words "a", "aa", "aaa", there are exponentially many ways to cut the as, and every one of them fails at the b.

    Instead, answer a smaller question for each prefix: can the first i characters be split into words? Call the answer dp[i]. The empty prefix needs no words, so dp[0] is true, and the final answer is dp[n] for a string of length n.

    A prefix of length i can be split exactly when it ends with some dictionary word w and the part before that word can be split. 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 on spell w. Each dp[i] uses only shorter prefixes, so filling the table from left to right works.

    For "leetcode" and {"leet", "code"}, the table for lengths 0 to 8 is:

    True False False False True False False False True

    Length 4 is true because "leet" follows the empty prefix. Length 8 is true because "code" follows the prefix of length 4, which is already true.

    Step by step

    1. Store s.Length in n. The table has an entry for every prefix length from 0 to n, so this number comes up often.
    2. Create dp as new bool[n + 1]. A new bool array is all false: a prefix counts as splittable only once a split is found.
    3. Set dp[0] to true. Every split starts from the empty prefix.
    4. Loop i from 1 to n inclusive. The last length, n, is the whole string.
    5. Loop over the words with foreach. Each word is tried as the last word of the prefix of length i.
    6. Compute start = i - word.Length, the index where the word would begin. It is negative when the word is longer than the prefix.
    7. Test three conditions joined by &&: start >= 0, then dp[start], then the substring comparison. && stops at the first false, so dp[start] is never read with a negative index, and the text is compared only when the earlier part already splits.
    8. Set dp[i] to true inside the if. One word that works is enough.
    9. Return dp[n] after the outer loop.

    The solution in C#

    class Solution {
    public bool WordBreak(string s, string[] wordDict) {
        int n = s.Length;
        bool[] dp = new bool[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            foreach (string word in wordDict) {
                int start = i - word.Length;
                if (start >= 0 && dp[start] && s.Substring(start, word.Length) == word) {
                    dp[i] = true;
                }
            }
        }
        return dp[n];
    }
}

    The C# details worth knowing:

    • s.Substring(start, word.Length) takes a length, not an end index: word.Length characters beginning at start. It throws ArgumentOutOfRangeException if the range does not fit inside the string, which is why start >= 0 is checked first. Because start + word.Length equals i, the range always ends inside s.
    • In C#, == on two strings compares their characters, so the comparison with word works as it reads.
    • foreach over a string[] reads each word in turn. The loop never changes the array.
    • Each Substring call creates a new string. That is fine for the constraints here (strings up to 300 characters).

    Complexity

    Time: O(n * m * k), where n is the length of s, m the number of words and k the length of the longest word. The table has n + 1 entries, each tries m words, and one comparison costs up to k characters.

    Space: O(n) for the table.

    When the dictionary is large, you can put the words in a HashSet<string> and, for each i, look up only the pieces of length 1 to k that end at i.

    A variant is useful when the dictionary is large and words are short. Put the words in a HashSet<string>, and for each i test only the pieces of length 1 to 20 that end at i:

    public bool WordBreak(string s, string[] wordDict) {
    HashSet<string> words = new HashSet<string>(wordDict);
    int n = s.Length;
    bool[] dp = new bool[n + 1];
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int len = 1; len <= 20 && len <= i; len++) {
            if (dp[i - len] && words.Contains(s.Substring(i - len, len))) { dp[i] = true; break; }
        }
    }
    return dp[n];
}

    The limit 20 is the longest word the constraints allow. It gives the same answers on the three examples and on "abcd" with {"ab", "abc", "d"}: True, True, False and True for that last one. In a file of your own it needs using System.Collections.Generic;.

    Edge cases and common mistakes

    • Leftover characters. "aba" with {"ab"} returns false: the a at the end has no word.
    • Reusing a word. "aaaaaaab" with {"a", "aa", "aaa"} returns false quickly, because the table never marks length 8 as splittable. Words may repeat, so the loop over the words restarts for every i.
    • Forgetting dp[0] = true. Then no prefix can ever become true, and every answer is false.
    • Looping only to n - 1. The table needs dp[n], so the loop condition is i <= n.
    • Greedy matching. Taking the first word that matches at the front can fail: for "abcd" with {"ab", "abc", "d"}, starting with "ab" leaves "cd", but "abc" + "d" works and the answer is True. The table tries every word at every position.

    Testing

    • "leetcode" with {"leet", "code"} gives True.
    • "applepenapple" with {"apple", "pen"} gives True.
    • "catsandog" with {"cats", "dog", "sand", "and", "cat"} gives False.
    • "aaaaaaab" with {"a", "aa", "aaa"} gives False.
    • "aba" with {"ab"} gives False.
    • "abcd" with {"ab", "abc", "d"} gives True.
    • "a" with {"a"} gives True.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free