Word Break Problem

Leetcode: Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaceGiven 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. You may assume the dictionary does not contain duplicate words..

Return all such possible sentences.

For example, given

s = "catsanddog"

dict = ["cat", "cats", "and", "sand", "dog"].

returns true

The problem can be solved using Dynamic Programming.

  1. Start traversing the string from index 0. At index 0 , substring 'c' is not in dict.
  2. Substring ca is not in dict
  3. Substring cat is in dict. Now there is two possibility as it can be seen in the diagram. consider cat as part of answer and traverse forward with substring sanddog and ignore cat and look for next substring which is cats.
  4. Follow above steps till the end of the string. If by the end of string, it can be split into multiple words then return true

Note: If we follow above approach then same subproblems will be evaluated multiple times. This can be avoided by mapping out the iteration on a 2d array.

  1. Create boolean 2d array of size mat[n][n]
  2. Start a for loop l = 1...n. The value of l defines the length of the prefix
  3. Start from i=0... s.length()-l+1 and set value of j= i+l-1
  4. Get substring of length i..j. If the substring is present in dict mark mat[i][j] = true
  5. If the prefix is present in the dict mark mat[i][j]=true
  6. if not then for k=i..j set mat[i][j] = true if mat[i][k]=true && mat[k][j] = true
  7. After iterating through all prefixes return mat[0][n-1]
public class WordBreak {

  public static void main(String[] args) {
    List dict = new ArrayList<>();
    dict.add("cat");
     dict.add("cats");
     dict.add("and");
     dict.add("sand");
     dict.add("dog");
     System.out.println(new WordBreak().wordbreak("catsanddog", dict));
  }

  public boolean wordbreak(String words, List dict) {
    boolean mat[][] = new boolean[words.length()][words.length()];
    for (int i = 0; i < words.length(); i++)
      mat[i][i] = dict.contains(words.charAt(i)+"");
    for (int l = 2; l <= words.length(); l++) {
      for (int i = 0; i < words.length() - l + 1; i++) {
        int j = i + l - 1;
        if (dict.contains(words.substring(i, j+1))) {
          mat[i][j] = true;
          continue;
        }
        for (int k = i; k < j; k++) {
          if (mat[i][k] == true && mat[k+1][j] == true) {
            mat[i][j] = true;
            continue;
          }
        }
      }
    }
    return mat[0][words.length() - 1];
  }
}

The time complexity of above solution is O(n^3). This can be optimized too.

public class Solution {
   
  public boolean wordBreak(String s, List<String> wordDict) {
    boolean[] f = new boolean[s.length() + 1];
    f[0] = true;
    for (int i = 1; i <= s.length(); i++) {
      for (int j = 0; j<i; j++) {
        if (f[j] && wordDict.contains(s.substring(j, i))) {
          f[i] = true;
          break;
        }
      }
    }
    return f[s.length()];
  }
}