Lexi's Leetcode solutions

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

Posted on: October 6, 2013

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);
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: