 }
 
     
-class TrieNode {
-    var isEnd: Bool
-    var letter: Character
-    var children: [Character: TrieNode]
-  
-    init(_ letter: Character) {
-        self.isEnd = false
-        self.letter = letter
-        self.children = [Character: TrieNode]()
-    }
-}
-
-
 class Trie {
-    var root: TrieNode?
+    var root: TrieNode
   
     init() {
-        root = TrieNode(Character("0"))
+        root = TrieNode()
     }
   
     func insert(_ word: String) {
         var node = root
+        var word = [Character](word.characters)
     
-        for char in word {
-            if node?.children[char] == nil {
-                node?.children[char] = TrieNode(char)
+        for i in 0 ..< word.count {
+            let c = word[i]
+      
+            if node.children[c] == nil {
+                node.children[c] = TrieNode()
             }
       
-            node = node?.children[char]
+            node = node.children[c]!
         }
     
-        node?.isEnd = true
+        node.isEnd = true
     }
   
-    func search(_ word: String) -> Bool {
+    func isWord(_ word: String) -> Bool {
         var node = root
+        var word = [Character](word.characters)
     
-        for char in word {
-            guard let childTrieNode = node?.children[char] else {
+        for i in 0 ..< word.count {
+            let c = word[i]
+      
+            if node.children[c] == nil {
                 return false
             }
       
-            node = childTrieNode
+            node = node.children[c]!
         }
     
-        return node?.isEnd
+        return node.isEnd
     }
-  
-    func start(with word: String) -> Bool {
+        
+    func isWordPrefix(_ prefix: String) -> Bool {
         var node = root
+        var prefix = [Character](prefix.characters)
     
-        for char in word {
-            guard let childTrieNode = node?.children[char] else {
+        for i in 0 ..< prefix.count {
+            let c = prefix[i]
+      
+            if node.children[c] == nil {
                 return false
             }
       
-            node = childTrieNode
+            node = node.children[c]!
         }
     
         return true
     }
 }
+
+class TrieNode {
+    var isEnd: Bool
+    var children: [Character:TrieNode]
+  
+    init() {
+        isEnd = false
+        children = [Character:TrieNode]()
+    }
+}
        visited[i][j] = false
    }
    
    func _convertToTrie(words: [String]) -> Trie {
        let trie = Trie()
  
        for str in words {

 */

class WordSearchII {
    
    func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
        var res = [String]()
  
        let m = board.count
        let n = board[0].count

        let trie = _convertToTrie(words)
        var visited = [[Bool]](repeating: Array(repeating: false, count: n), count: m)
  
        for i in 0 ..< m {
            for j in 0 ..< n {
                _dfs(board, m, n, i, j, &visited, &res, trie, "")
            }
        }
