[leetcode] Word Break | 二分法看一个词是不是能用字典里的词组成

Posted by: lexigrey on: October 6, 2013

• In: classic | leetcode
• Leave a Comment

这题leetcode把关太松了，一个cache就让过了。实际上应该再加一个prefix tree把关，比如leetcode， le如果发现连个prefix都不是，那么lee, leet, leetc..都不要查了。所以算法是：

1. 拿字典建prefix tree：O(字典大小*最长词的长度）
2. i=0开始recurse, j=i开始一点点增长当前substring长度，若curr substring在字典里，就看看j + 1开头的剩下一半能不能成；能成就直接返回true，不能的话还得继续i++
3. curr substring不在字典里，那应该j++的，但这时候先看一看curr是不是至少是个prefix，要是连prefix都不是，这个i直接作废，i++
4. 每次做好了cache一下，boolean cache[i]表示以i开头到词尾的这个substring能不能用字典组成

public class Node {
  char c;
  Node[] children;
  public Node (char ch){
    c = ch;
    children = new Node[26];
  }
}
public boolean wordBreak(String s, Set<String> dict) {
  if (s == null || s.length() == 0)
    return false;
  return canSplit(s, dict, 0, new HashMap<Integer, Boolean>(), makePrefixTree(dict));
}
private Node makePrefixTree(Set<String> dict) {
  Node root = new Node('0');
  for (String s : dict) {
    insertWord(root, s);
  }
  return root;
}
private void insertWord(Node root, String s) {
  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    if (root.children[c - 'a'] == null) {
      root.children[c - 'a'] = new Node(c);
    }
    root = root.children[c - 'a'];
  }
}
private boolean canSplit(String s, Set<String> dict, int i, HashMap<Integer, Boolean> cache, Node root) {
  if (i == s.length())
    return true;
  if (cache.containsKey(i))
    return cache.get(i);
  boolean canSplit = false;
  for (int j = i; j < s.length(); j++) {
    String first = s.substring(i, j + 1);
    if (dict.contains(first)) {
      if (canSplit(s, dict, j + 1, cache, root)) {
        canSplit = true;
        break;
      } //cannot split to the end, try split by i, j + 1
    } else {
      //does not contain first word, try split by i, j + 1
      if (!containsAsPrefx(first, root)) {
        //does not even contain first word as prefix, then can't start by i, split by i + 1
        break;
      }
    }
  }
  cache.put(i, canSplit);
  return cache.get(i);
}
private boolean containsAsPrefx(String s, Node root) {
  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    if (root.children[c - 'a'] == null)
      return false;
    root = root.children[c - 'a'];
  }
  return true;
}

Tags: 二分法