I was attempting to solve LeetCode 139 - Word Break

Here is a short example of what this question asks:

I watched some videos saying implementing a trie would be an efficient approach to solve this so I implemented a Trie as follows:

fileprivate class TrieNode {
    var data: Character?
    var isWordEnd = false
    var next = [Character: TrieNode]()
}

fileprivate struct Trie {
    var root = TrieNode()
    
    func insert(_ word: String) {
        var rootNode = root
        
        for char in word {
            rootNode = insertInternal(char, at: rootNode)
        }
        
        rootNode.isWordEnd = true
    }
    
    func insertInternal(_ char: Character, at node: TrieNode) -> TrieNode {
        var nextNode = TrieNode()
        
        if node.next[char] != nil {
            nextNode = node.next[char]!
        }
        
        nextNode.data = char
        node.next[char] = nextNode
        return nextNode
    }
    
    func doesWordExist(_ word: String) -> Bool {
        var rootNode = root
        
        for char in word {
            let nextNode = rootNode.next
            if nextNode[char] == nil {
                return false
            }
            
            rootNode = nextNode[char]!
        }
        
        return rootNode.isWordEnd
    }
}

Then in order to solve the problem, I took the recursion / backtracking approach with the help of the Trie created above in the following way:

func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
    let trie = Trie()
    
    for word in wordDict {
        trie.insert(word)
    }
    
    return wordBreakInternal(s, wordDict: trie)
}

fileprivate func wordBreakInternal(_ s: String, wordDict: Trie) -> Bool {
    if s.isEmpty { return true }
    
    let leftIndex = s.startIndex
    var rightIndex = s.startIndex
    
    while rightIndex < s.endIndex {
        let word = String(s[leftIndex ... rightIndex])
        
        if wordDict.doesWordExist(word) {
            var nextStartIndex = rightIndex
            s.formIndex(after: &nextStartIndex)
            let nextWord = String(s[nextStartIndex ..< s.endIndex])
            
            if wordBreakInternal(nextWord, wordDict: wordDict) {
                return true
            }
        }
        
        s.formIndex(after: &rightIndex)
    }
    
    return false
}

I feel the solution works in terms of giving the desired output for these test cases:

print(wordBreak("leetcode", ["leet","code"])) // true
print(wordBreak("applepenapple", ["apple","pen"])) // true
print(wordBreak("catsandog", ["cats","dog","sand","and","cat"])) // false
print(wordBreak("aaaaaaa", ["aaaa","aaa"])) // true

However, when a large string is the input:

s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

wordDict = ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

I get Time Limit Exceeded in my LeetCode submission.

Could someone advice if the optimization needs to be done in my trie implementation or in my backtracking / recursion with some ideas on how to make things more efficient ?