内容简介:Design a data structure that supports the following two operations:void addWord(word)bool search(word)
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 letters a-z or .. A . means it can represent any one letter.
Example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.
难度:medium
题目:
设计数据结构支持以下两操作:
void addWord(word)
bool search(word)
search(word) 可以查单词或包含.的正则表达式。 .可以表示任何单个字符。
注意:
你可以假定所有单词仅由小写字母组成。
思路:
Tire Tree, DFS
Runtime: 94 ms, faster than 89.57% of Java online submissions for Add and Search Word - Data structure design.
class WordDictionary { private TrieNode root; /** Initialize your data structure here. */ public WordDictionary() { root = new TrieNode(); } /** Adds a word into the data structure. */ public void addWord(String word) { char c = word.charAt(0); int i = 0, idx = 0; TrieNode ptr = root; for (; i < word.length(); i++, ptr = ptr.next[idx]) { idx = word.charAt(i) - 'a'; if (null == ptr.next[idx]) { ptr.next[idx] = new TrieNode(); } } ptr.isWord = true; } // dfs /** 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) { return search(word, 0, root); } public boolean search(String word, int idx, TrieNode beginNode) { if (idx >= word.length() || null == beginNode) { return false; } TrieNode node = null; int c = word.charAt(idx), cIdx = c - 'a'; if ('.' == c) { boolean result = false; for (int i = 0; i < 26; i++) { node = beginNode.next[i]; if (null == node) { continue; } if ((idx + 1) == word.length() && node.isWord) { return true; } result = result || search(word, idx + 1, beginNode.next[i]); } return result; } // c is not equal to '.' node = beginNode.next[cIdx]; if (null == node) { return false; } if ((idx + 1) == word.length()) { return node.isWord; } return search(word, idx + 1, beginNode.next[cIdx]); } public static class TrieNode { public boolean isWord; public TrieNode[] next = new TrieNode[26]; } } /** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * boolean param_2 = obj.search(word); */
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。