Word Break

Problem

Word Break

Given a non-empty string and an array of non-empty words, determine if s can be composed by one or more words in the array.

For exampl, 

Given string "atigerisacat" and array [a, tiger, is, cat, deer, mice, not].

Output: true

Given string "twotigersarestillcats" and array [a, tiger, is, cat, deer, mice, not].

Output: false

Solution

We need to exam the string recursively. For a given start index, we increase the end index, then exam if substring(star, end) is in the dictionary. If yes, we then set start = end, then recursively validate the substring(start). Since we validated many substrings again and again in the caller stack, we can trade space for speed by memorize those result. Thus the call stack won't be larger than N. Therefore, the time cost is O(N^2) and space cost is O(N).

import java.util.*;
public class WordBreak {
  public static boolean canBreak(String str, List<String> dic, int start, Boolean[] memo) {
    if(start == str.length()) return true;
    if(memo[start] != null) return memo[start];
    for(int end = start + 1; end <= str.length(); end++) {
      if(dic.contains(str.substring(start, end)) && canBreak(str, dic, end, memo)) {
        memo[start] = true;
        return true;
      }
    }
    memo[start] = false;
    return false;
  }
  public static void main(String...args) {
    String[] dic = new String[]{"a", "tiger", "is", "cat", "deer", "mice", "not"};
    String s = "atigerisacat";
    Boolean[] memo = new Boolean[s.length()];
    System.out.println(canBreak(s, Arrays.asList(dic), 0, memo));
    s = "twotigersarestillcats";
    memo = new Boolean[s.length()];
    System.out.println(canBreak(s, Arrays.asList(dic), 0, memo));
  }
}

Time complexity O(N^2), space complexity O(N).