[leetcode] Word Break 2 | 把string所有能用dict组成的组法print出来

Posted by: lexigrey on: October 6, 2013

• In: leetcode
• Leave a Comment

For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"], the solution is ["cats and dog", "cat sand dog"]

这题是cache里面存数组: Map<Integer, List<String>> cache，和上题思路一样，不过边界条件不好想：

• 找不到的时候是返回空list还是null?
• 找到结尾正好成功了(i == string.len)的时候，返回空还是null?

这两种情况必须区分。因为要在每个list entry里生成新的substring，所以还是找不到的时候返回空list比较好（空的正好不用进loop了）；而找到头的时候，刚好check null，然后把当前词尾返回，catch了最后一个词不用加” “的情况。

public ArrayList<String> wordBreak(String s, Set<String> dict) {
  if (s == null || s.length() == 0)
    return new ArrayList<String>();
  HashMap<Integer, ArrayList<String>> cache = new HashMap<Integer, ArrayList<String>>();
  return split(s, dict, 0, cache);
}
private ArrayList<String> split(String s, Set<String> dict, int i, HashMap<Integer, ArrayList<String>> cache) {
  if (i == s.length())
    return null;
  if (cache.containsKey(i))
    return cache.get(i);
  ArrayList<String> result = new ArrayList<String>();
  for (int j = i; j < s.length(); j++) {
    String curr = s.substring(i, j + 1);
    if (dict.contains(curr)) {
      ArrayList<String> rest = split(s, dict, j + 1, cache);
      if (rest == null) {
        StringBuilder sb = new StringBuilder();
        sb.append(curr);
        result.add(sb.toString());
      } else {
        for (String tail : rest) {
          StringBuilder sb = new StringBuilder();
          sb.append(curr).append(" ").append(tail);
          result.add(sb.toString());
        }
      }
    }
  }
  cache.put(i, result);
  return cache.get(i);
}

Tags: 1WayDP, 二分法