- Difficulty: Medium
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.
For 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
You may assume that all words are consist of lowercase letters
a-z
.
思路:按照Trie写data structure, when meet '.', we need do back tracking.
Base case is index == chs.length since root is NULL
Complexity: worst case of all '...' it will check all nodes of trie, O(26^n) n is key length
关键字: dfs, Trie
Base case is index == chs.length since root is NULL
Complexity: worst case of all '...' it will check all nodes of trie, O(26^n) n is key length
关键字: dfs, Trie
public class WordDictionary { //data structure public class TrieNode{ public TrieNode[] links = new TrieNode[26]; public boolean isEnd; } private TrieNode root = new TrieNode(); // Adds a word into the data structure. public void addWord(String word) { TrieNode node = root; for(int i=0;i<word.length();i++){ char cur = word.charAt(i); if(node.links[cur-'a']==null) node.links[cur-'a'] = new TrieNode(); node = node.links[cur-'a']; } node.isEnd = true; } // 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) { //need backtracking return match(word.toCharArray(),0,root); } public boolean match(char[] chs,int index,TrieNode node){ if (index == chs.length) return node.isEnd;//because root is NULL if (chs[index] != '.') { return node.links[chs[index] - 'a'] != null && match(chs, index + 1, node.links[chs[index] - 'a']); } else {//backtracking: set of options which is links[i],try each recursively for (int i = 0; i < node.links.length; i++) {//recur any links of '.' if (node.links[i] != null && match(chs, index + 1, node.links[i])) { return true;//if there is match, we just return true }//if not match, we just skip to next one, until no char left and we ensure no match } } return false; } } // Your WordDictionary object will be instantiated and called as such: // WordDictionary wordDictionary = new WordDictionary(); // wordDictionary.addWord("word"); // wordDictionary.search("pattern");
No comments:
Post a Comment