I was attempting to solve LeetCode 139 - Word Break
Given a string
s
and a dictionary of stringswordDict
, returntrue
ifs
can be segmented into a space-separated sequence of one or more dictionary words.Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: falseConstraints:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s
andwordDict[i]
consist of only lowercase English letters.- All the strings of wordDict are unique.
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 ?