Word Break

• 暴力递归

  • 平均复杂度为O(n!),最差为s="aaaa...aaa", dict=['a','aa','aaa', ...], O(n^n)

  • 递推的定义是：从start开始到s的最末，是否满足word break

    class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
      //turn list into set
      HashSet<String> set = new HashSet<>();
    
      for (int i = 0; i < wordDict.size(); i++) {
          set.add(wordDict.get(i));
      }
    
      if (set.contains(s)) return true;        
      return helper(s, set, 0);       
    }
    
    public boolean helper(String s, Set<String> dict, int start) {
    
      if (start == s.length()) return true;
    
      for (int i = start+1; i <= s.length(); i++) { 
          String sub = s.substring(start, i);
          if (dict.contains(sub) && helper(s, dict, i)) {
              return true;                    
          }
      }
    
      return false;        
    }
    }
    

• 记忆化递归 (memo array)

  • 通过递归发现，有很多的重复计算，这就要考虑到保存从尾端算起的长度数列，如果已经计算过了，就可以直接运用结果
  • 注意这里用的是Boolean(a.k.a Object)而非boolean (primitive type)，因为保存的是计算结果可能为true也可能为false，所以要用Object，当为赋值的时候为null
  • O(n^2)

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return word_Break(s, new HashSet(wordDict), 0, new Boolean[s.length()]);
    }
    public boolean word_Break(String s, Set<String> wordDict, int start, Boolean[] memo) {
        if (start == s.length()) {
            return true;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, memo)) {
                return memo[start] = true;
            }
        }
        return memo[start] = false;
    }
}

• BFS
  • 画BFS树，注意这里，queue保存的是每个分割点
  • 同时，需要用一个visited数组，记录已经访问过的节点。这是为了处理当字典里存在['a', 'aa', 'aaa',...], s='aaaaa...aaa' 这样的case
  • 每个起始点都搜索整个given string

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {

        HashSet<String> dict = new HashSet(wordDict);
        //store the position into the queue
        Queue<Integer> queue = new LinkedList<>();
        int[] visited = new int[s.length()];

        queue.add(0);

        while (!queue.isEmpty()) {
            int start = queue.remove();

            if (visited[start] == 0) {
                for (int i = start + 1; i <= s.length(); i++) {
                    String str = s.substring(start, i);
                    if (dict.contains(str)) {
                        queue.add(i);
                        if (i == s.length()) return true;
                    }
                }
            }            
            visited[start] = 1;
        }        
        return false;
    }
}

• DP
  • 可以分为两个不同的子问题，如果这两个子问题分别满足，那么就可以满足。
  • dp[i]定义为以ith为结尾的string是否可以wordbreak
    • 其通项则为从0到i是否满足, dp[j]==true && set.contains[substring(j,i)]
  • 但是由于substring,注意初始化dp[s.length()+1]

Word Break II

• HashMap, key是index, value为以这个index组成的strings.这样可以减少重复的visited