648. Replace Words

class Solution {
    func replaceWords(_ dict: [String], _ sentence: String) -> String {
        let trie = Trie()
        for w in dict {
            trie.addWord(w)
        }
        let arr = sentence.split(separator: " ")
        var res = [String]()
        for word in arr{
            let charArr = Array(word)
            var found = false
            for i in 1 ... charArr.count{
                if trie.hasPrefix(String(charArr[0 ..< i])){
                    if trie.hasWord(String(charArr[0 ..< i])){
                       res.append(String(charArr[0 ..< i]))
                        found = true
                        break
                    }
                }else{
                    break
                }
            }
            if !found {
                res.append(String(word))
            }
        }

        return res.joined(separator: " ")
    }


    class Trie {
        var root : Node
        init(){
            root = Node()
        }

        func addWord(_ word : String){
            var runner = root
            for char in word{
                if let next = runner.children[char]{
                    runner = next
                }else {
                    let next = Node()
                    runner.children[char] = next
                    runner = next
                }
            }
            runner.hasWord = true
        }
        func hasPrefix(_ pre:String) -> Bool{
            var runner = root
            for char in pre{
                if let next = runner.children[char]{
                    runner = next
                }else {
                   return false
                }
            }
            return true
        }
        func hasWord(_ w:String) -> Bool{
            var runner = root
            for char in w{
                if let next = runner.children[char]{
                    runner = next
                }else {
                   return false
                }
            }
            return runner.hasWord
        }
    }
    class Node{
        var children : [Character : Node]
        var hasWord : Bool
        init(){
            children = [Character : Node]()
            hasWord = false
        }
    }
}