Lexi's Leetcode solutions

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

Posted on: October 6, 2013

这题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:

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: