212. Word Search II

class Trie {
    var root = Node()
    func addWord( _ str: String){
        var runner = root
        for char in str{
            if let childN = runner.child[char]{
                runner = childN
            }else{
                runner.child[char] = Node()
                runner = runner.child[char]!
            }
        }
        runner.hasWord = true
    }
    func hasPrefix(_ pre: String) -> Bool{
        var runner = root
        for char in pre{
            if let childN = runner.child[char]{
                runner = childN
            }else{
               return false
            }
        }
        return true
    }
    func hasWord(_ word : String) -> Bool{
        var runner = root
        for char in word{
            if let childN = runner.child[char]{
                runner = childN
            }else{
               return false
            }
        }
        return runner.hasWord
    }
}

class Node{
    var child = [Character : Node]()
    var hasWord = false
}

class Solution {
    func findWords(_ b: [[Character]], _ words: [String]) -> [String] {
        var ans = [String]()
        var trie = Trie()
        for w in words {
            trie.addWord(w)
        }
        var visited = [[Bool]](repeating : [Bool](repeating: false, count: b[0].count ), count : b.count)
        for i in 0 ..< b.count{
            for j in 0 ..< b[0].count{
                var list = ""
                dfs(b,i, j, &ans, trie, &list, &visited)
            }
        }
        return ans
    }

    let dx = [0,0,1,-1]
    let dy = [1,-1,0,0]
    func dfs(_ b: [[Character]], _ x: Int, _ y :Int, _ ans: inout [String], _ trie: Trie, _ list: inout String, _ visited :inout [[Bool]]){
        list.append(b[x][y])

        if !trie.hasPrefix(list) {
            list.removeLast()
            return
        }
        if trie.hasWord(list) && !ans.contains(list){
            ans.append(list)
        }
        visited[x][y] = true
        for i in 0 ..< 4{
            let nx = dx[i] + x
            let ny = dy[i] + y
            if nx >= 0 && ny >= 0 && ny < b[0].count && nx < b.count && !visited[nx][ny]{
                dfs(b,nx, ny, &ans, trie, &list, &visited)

            }
        }
        list.removeLast()
        visited[x][y] = false
    }
}