[leetcode] Word Break | 二分法看一个词是不是能用字典里的词组成
Posted October 6, 2013
on:- In: classic | leetcode
- Leave a Comment
这题leetcode把关太松了,一个cache就让过了。实际上应该再加一个prefix tree把关,比如leetcode, le如果发现连个prefix都不是,那么lee, leet, leetc..都不要查了。所以算法是:
- 拿字典建prefix tree:O(字典大小*最长词的长度)
- i=0开始recurse, j=i开始一点点增长当前substring长度,若curr substring在字典里,就看看j + 1开头的剩下一半能不能成;能成就直接返回true,不能的话还得继续i++
- curr substring不在字典里,那应该j++的,但这时候先看一看curr是不是至少是个prefix,要是连prefix都不是,这个i直接作废,i++
- 每次做好了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