Swift: Trie + DFS with complexity analysis
Complexity Analysis:\nWe use "n" as the length of the string being added,\n\nFor add():\nTime: O(n), Space: O(n)\n\nFor search():\n- When there are no wildcards
Complexity Analysis:\nWe use "n" as the length of the string being added,\n\nFor add():\nTime: O(n), Space: O(n)\n\nFor search():\n- When there are no wildcards: \nTime: O(n), Space: O(n) because of the recursive calls\n- Where there are wildcards:\nThe absolute worst case we can have 26 children at each node, traversing through all nodes with DFS will take 26^n (n nodes, each nodes have 26 children/characters). 26^n is technically 2^n. Therefore,\nTime: O(2^n), Space: O(n) because we only have at max n calls on the stack at any given time.\nHowever, one can use tighter bounds and say Time: O(m) where m is the total number of characters on the trie.\n\n\n```\nclass Trie {\n    var isEnd = false\n    var dict = [Character : Trie]()\n}\n\nclass WordDictionary {\n    let root = Trie()\n    \n    func addWord(_ word: String) {\n        var node = root\n        for char in word {\n            if node.dict[char] == nil { node.dict[char] = Trie() }\n            node = node.dict[char]!\n        }\n        node.isEnd = true\n    }\n    \n    func search(_ word: String) -> Bool {\n        return dfs(0, Array(word), root)\n    }\n    \n    func dfs(_ index: Int, _ word: [Character], _ node: Trie) -> Bool {\n        if index == word.count { return node.isEnd }\n        let char = word[index]\n        if char != "." {\n            return node.dict[char] != nil && dfs(index + 1, word, node.dict[char]!)\n        } else {\n            for ch in node.dict.keys {\n                if node.dict[ch] != nil && dfs(index + 1, word, node.dict[ch]!) {\n                    return true\n                }\n            }\n        }\n        \n        return false\n    }\n}\n```
['Depth-First Search', 'Trie', 'Swift']