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 in addWord consists of lowercase English letters.

word in search 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 and search.

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:

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: &currentIndex)
                continue
            }
            
            return false
        }
        
        return currentNode.isWordEnd
    }
    
    return dfs(index: word.startIndex, at: root)
}

It currently fails at 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.