139. Word Break

/**

 * 139. Word Break

 * Given a non-empty string s and a dictionary wordDict containing a list of non-empty words,

 * determine if s can be segmented into a space-separated sequence of one or more dictionary words.

 * Note:

 * The same word in the dictionary may be reused multiple times in the segmentation.

 * You may assume the dictionary does not contain duplicate words.

 * Example 1:

 * Input: s = “leetcode”, wordDict = [“leet”, “code”]

 * Output: true

 * Explanation: Return true because “leetcode” can be segmented as “leet code”.

 */

See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/WordBreak.java

Observation:

  • You can work incrementally from left to right to match the string with the words
  • For any string you can divide it into a part starting from first index to a given index and then another from the given index to the end of the string. If left and right parts have a match then the whole string has a match.
  • We can utilize dynamic programming for this problem.

Algorithm:

  • Create a dp array of length equal to total length of string + 1
  • Initialize first index 0, in dp array to true
  • From index 1 of string on to end of string iteratively
    • Iterate the string over left segment starting from 0 onto the end of segment
      • If left segment matches, check if right segment forms a word that exists in dictionary
      • If the above condition holds, mark the index on right segment as true to signify that words in the dictionary can be used to form the substring up to the given index and break

Here is the dp based solution for this problem:

(the github code also includes a recursive memorization-based solution.)

public boolean wordBreakDP(String s, List<String> wordDict) {
    Set<String> wordDictSet = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}