Return to Answer

The code then looks like this:

class WordDictionary {
 var root: TrieNode
 var cache: [String: Bool] = [:]
 var cacheValid = true
 
 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
 cacheValid = false
 }
 
 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 {
 if (!cacheValid) {
 let falseKeys = cache.compactMap { 0ドル.value == false ? 0ドル.key : nil }
 for key in falseKeys {
 cache[key] = nil
 }
 cacheValid = true
 } else if let result = cache[word] {
 return result
 }
 
 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 == "." {
 for nextNode in currentNode.next.values {
 let nextIndex = word.index(currentIndex, offsetBy: 1)
 if dfs(index: nextIndex, at: nextNode) {
 return true
 }
 }
 return false
 }
 
 if let nextNode = currentNode.next[currentChar] {
 currentNode = nextNode
 word.formIndex(after: &currentIndex)
 } else {
 return false
 }
 }
 
 return currentNode.isWordEnd
 }
 
 let result = dfs(index: word.startIndex, at: root)
 cache[word] = result
 return result
 }
}

This can be optimized further:

• Repeated calls to cache.removeAll() can be avoided. Instead of emptying the cash in addWord(), set an "invalid" flag and empty the cache in the search() method if that flag is set.

• true entries in the cache remain valid if a new word is added to the dictionary. So instead of completely emptying the cache if a new word has been added, remove only the false entries.