mock_interview_3

word_break.java

/*

s = "applepenapple" dictionary = ["apple", "pen"]
s = "apple" + "pen" + "apple"
return True


s = "appplepearapple" dictionary = ["apple", "pen"]
return False

0 <= len(s) <= 10^5
0 <= len(dictonary) <= 10^5
*/

// dp[i] should be the result of the this problem for s[0:i]
// i, j j <= i; dp[j] && set.contains(j, i) 

public boolean wordBreak(String s, List<String> wordDict) {
  Set<String> set = new HashSet<>();
  for (int i = 0; i < wordDict.size(); i++) {
    set.add(wordDict.get(i));
  }

  boolean[] dp = new boolean[s.length() + 1];
  dp[0] = true;

  for (int i = 1; i < dp.length; i++) {
    for (int j = 0; j <= i; j++) {
      	dp[i] = dp[j] && set.contains(s.substring(j, i));
      	if (dp[i]) {
        	break;	
        }
    }
  }
  return dp[s.length()];
}