leetcode 211: Add and Search Word

Add and Search Word – Data structure designTotal Accepted: 1221 Total Submissions: 6120

Design a data structure that supports the following two operations:

void addWord(word)bool search(word)

search(word) can search a literal word or a regular expression string containing only lettersa-z or.. A. means it can represent any one letter.

For example:

addWord("bad")addWord("dad")addWord("mad")search("pad") -> falsesearch("bad") -> truesearch(".ad") -> truesearch("b..") -> true

Note:You may assume that all words are consist of lowercase letters a-z.

[思路]

1. 用一个set存. 超时.

2. 用trie来存.

[CODE]

public class WordDictionary {Set<String> dict = new HashSet<String>();// Adds a word into the data structure.public void addWord(String word) {dict.add(word);}// Returns if the word is in the data structure. A word could// contain the dot character '.' to represent any one letter.public boolean search(String word) {if(dict.contains(word) ) return true;else if(!word.contains(".")) return false;for(int c='a'; c<='z'; c++) {int i=0;while(word.charAt(i++) != '.'){}StringBuilder sb = new StringBuilder(word);sb.setCharAt(i-1, (char)c);if( search(sb.toString()) ) return true;}return false;}}2. 先建一个Trie, 然后搜索即可

public class WordDictionary {private TrieNode root = new TrieNode();public void addWord(String word) {Map<Character, TrieNode> children = root.children;for(int i=0; i<word.length(); i++) {char c = word.charAt(i);TrieNode t;if(children.containsKey(c)) {t = children.get(c);} else {t = new TrieNode(c);children.put(c, t);}children = t.children;if(i==word.length()-1) t.leaf=true;}}public boolean search(String word) {return searchNode(word, root);}public boolean searchNode(String word, TrieNode tn) {if(tn==null) return false;if(word.length() == 0 ) return tn.leaf;Map<Character, TrieNode> children = tn.children;TrieNode t = null;char c = word.charAt(0);if(c=='.') {for(char key : children.keySet() ) {if(searchNode(word.substring(1), children.get(key) )) return true;}return false;} else if(!children.containsKey(c)) {return false;} else {t = children.get(c);return searchNode(word.substring(1), t);}}}class TrieNode {// Initialize your data structure here.char c;boolean leaf;HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();public TrieNode(char c) {this.c = c;}public TrieNode(){};}

,感悟了不同的人生。凌晨,随着滑轮接触地面,

leetcode 211: Add and Search Word

相关文章:

你感兴趣的文章:

标签云: