I have been trying to solve Trie related problems over at leet code and came across this interesting problem 211. Design Add and Search Words Data Structure
Here is the question for convenience:
211. Design Add and Search Words Data Structure
Design a data structure that supports adding new words and finding if a string matches any previously added string.
Implement the WordDictionary class:
WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.
Example:
Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad"); wordDictionary.addWord("dad");
wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return
False wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
Constraints:
1 <= word.length <= 25
word
inaddWord
consists of lowercase English letters.
word
insearch
consist of '.' or lowercase English letters.There will be at most 3 dots in word for
search
queries.At most 104 calls will be made to
addWord
andsearch
.
I got some help yesterday with a similar question on how to optimize my Trie implementation and tried my best to incorporate those into my solution to this question.
I got a solution to work with Trie and backtracking, however, I once again ran into the Time Limit exceeded conundrum.
I came across this Python solution on Youtube and tried to implement it using Swift, however that did not help.
Here is the search function:
private class WordDictionary {
var root: TrieNode
class TrieNode {
var next = [Character: TrieNode]()
var isWordEnd = false
}
init() {
root = TrieNode()
}
func addWord(_ word: String) {
var node = root
for char in word {
node = addInternal(char, at: node)
}
node.isWordEnd = true
}
func addInternal(_ char: Character, at node: TrieNode) -> TrieNode {
if let nextNode = node.next[char] {
return nextNode
}
let nextNode = TrieNode()
node.next[char] = nextNode
return nextNode
}
func search(_ word: String) -> Bool {
func dfs(index: String.Index, at node: TrieNode) -> Bool {
var currentNode = node
var currentIndex = index
while currentIndex < word.endIndex {
let currentChar = word[currentIndex]
if currentChar == "." {
if let nextNodes = Array(currentNode.next.values) as? [TrieNode] {
for nextNode in nextNodes {
var nextIndex = currentIndex
word.formIndex(after: &nextIndex)
if dfs(index: nextIndex, at: nextNode) {
return true
}
}
}
return false
}
if let nextNode = currentNode.next[currentChar] {
currentNode = nextNode
word.formIndex(after: ¤tIndex)
continue
}
return false
}
return currentNode.isWordEnd
}
return dfs(index: word.startIndex, at: root)
}
}
This seems to be working correctly on these test cases:
private func test1() {
let wordDictionary = WordDictionary()
wordDictionary.addWord("baad")
wordDictionary.addWord("dad")
wordDictionary.addWord("mad")
print(wordDictionary.search("baa")) // return False
print(wordDictionary.search("bad")) // return False
print(wordDictionary.search("baad")) // return True
print(wordDictionary.search(".ad")) // return True
print(wordDictionary.search("b..d")) // return True
print(wordDictionary.search("pad")) // return False
print(wordDictionary.search("bad")) // return False
print(wordDictionary.search("b.ad")) // return True
print(wordDictionary.search("mad")) // return True
print(wordDictionary.search("bam")) // return False
}
private func test2() {
let wordDictionary = WordDictionary()
wordDictionary.addWord("a")
wordDictionary.addWord("a")
print(wordDictionary.search(".")) // return True
print(wordDictionary.search("a")) // return True
print(wordDictionary.search("aa")) // return False
print(wordDictionary.search("a")) // return True
print(wordDictionary.search(".a")) // return False
print(wordDictionary.search("a.")) // return False
}
However, I get a time limit exceeded exception on this test case
I am not sure where the bottle neck and as at first glance, I cannot see any opportunity for memoization to improve the performance.
I am sure there might be other / more optimal solutions besides using a Trie, however, I am trying to get an optimal solution using a Trie since I am currently trying to improve my understanding of this topic.