Word Break II Problem

Leetcode: Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. 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"].

A solution is ["cats and dog", "cat sand dog"]

The problem can be solved using Backtracking and memoization.

  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 add it to the answer list
  5. To optimize and prevent traversing same path multiple times using memoization
public class WordsBreak2 {

  public static void main(String[] args) {
    List dict = new ArrayList();
    dict.add("cat");
    dict.add("cats");
    dict.add("and");
    dict.add("sand");
    dict.add("dogs");
    System.out.println(new WordsBreak2().wordBreak("catsanddogs", dict));
  }

  public List wordBreak(String s, List wordDict) {
    if (s == null || s.isEmpty())
      return Collections.EMPTY_LIST;
    return wordBreak1(s, wordDict, new HashMap());
  }

  private List wordBreak1(String s, List wordDict, Map> map) {
    if (map.containsKey(s)) {
      return map.get(s);
    }
    List res = new ArrayList();
    System.out.println(s);
    for (int i = 1; i <= s.length(); i++) {
      // check if substring is present in dict.
      if (wordDict.contains(s.substring(0, i))) {
        if (s.substring(i).length() > 0) {
          // work with rest of the substring
          List r = wordBreak1(s.substring(i), wordDict);
          String w = s.substring(0, i);
          if (!r.isEmpty()) {
            for (String a : r) {
              res.add(w + " " + a);
            }
          }
        } else {
          res.add(s.substring(0, i));
        }
      }
    }
    map.put(s, res);
    return res;
  }

}

This is one approach but if you run this code in Leetcode you will get Time Limit Exceed error. For e.g.["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

Further optimization can be done by identifying the longest word in the dict and restricting the substring length not max of dict.

 public List wordBreak(String s, List wordDict) {
    if (s == null || s.isEmpty() || wordDict.size() == 0)
      return Collections.EMPTY_LIST;
    int length = getMaxLength(wordDict);
    return wordBreak1(s, wordDict, new HashMap(), length);
  }

  //find max length of word in dict
  private int getMaxLength(List wordDict) {
    return wordDict.stream().max((o1, o2) -> 
      Integer.compare(o1.length(), o2.length())).get().length();
  }

  private List wordBreak1(String s, List wordDict, Map> map, int maxLength) {
    if (map.containsKey(s)) {
      return map.get(s);
    }
    List res = new ArrayList();
    // restrict for loop with maxLength
    for (int i = 1; i <= maxLength && i <= s.length(); i++) {
      // check if substring is present in dict.
      if (wordDict.contains(s.substring(0, i))) {
        if (s.substring(i).length() > 0) {
          // work with rest of the substring
          List r = wordBreak1(s.substring(i), wordDict, map, maxLength);
          String w = s.substring(0, i);
          if (!r.isEmpty()) {
            for (String a : r) {
              res.add(w + " " + a);
            }
          }
        } else {
          res.add(s.substring(0, i));
        }
      }
    }
    map.put(s, res);
    return res;
  }

Another approach is to iterate over the dict and see if a word is present. The approach is very similar to above one, but here traversal of dict is done which is faster.

public class Solution {
    public List wordBreak(String s, List wordDict) {
    if (s == null || s.isEmpty())
      return Collections.EMPTY_LIST;
    return wordBreak1(s, wordDict, new HashMap());
  }

  private List wordBreak1(String s, List wordDict, Map> map) {
    if (map.containsKey(s)) {
      return map.get(s);
    }
    List res = new ArrayList();
    for (int i = 1; i <= s.length(); i++) {
      // System.out.println(s.substring(0, i));
      if (wordDict.contains(s.substring(0, i))) {
        if (s.substring(i).length() > 0) {
          List r = wordBreak(s.substring(i), wordDict);
          String w = s.substring(0, i);
          if (!r.isEmpty()) {
            for (String a : r) {
              res.add(w + " " + a);
            }
          }
        } else {
          res.add(s.substring(0, i));
        }
      }
    }
    map.put(s, res);
    return res;
  }

}