Word break

Decide whether a string can be split into a sequence of words taken from a dictionary.

The idea

dp[i] means the first i characters of s can be built from dictionary words. To fill it, try every earlier cut point j: if dp[j] is already true and the piece between j and i is a dictionary word, then dp[i] is true too.

Code

public static bool WordBreak(string s, HashSet<string> dict) {
    var dp = new bool[s.Length + 1];
    dp[0] = true;
    for (int i = 1; i <= s.Length; i++)
        for (int j = 0; j < i; j++)
            if (dp[j] && dict.Contains(s.Substring(j, i - j))) {
                dp[i] = true;
                break;
            }
    return dp[s.Length];
}

Tips

• A HashSet gives an O(1) dictionary lookup; a List would make every check O(words).
• Once dp[i] is found true, stop checking further cut points for that i.

In the .NET library

This counts whether a split exists, not the split itself. Recovering the actual words means also storing, for each true dp[i], which j made it true, then walking that chain backwards.