Swift Recursive DP Solution, Very Simple and Easy to Understand


  • 0
    Q
    class Solution {
        func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
            let wordSet = Set<String>(wordDict)
            var failedSet = Set<String>()
            return wordBreak(s, wordSet, &failedSet)
        }
        
        func wordBreak(_ s: String, _ wordSet: Set<String>, _ failedSet: inout Set<String>) -> Bool {
            if s.isEmpty {
                return true
            } else if failedSet.contains(s) {
                return false
            }
            
            let str = ArraySlice(s.characters)
            var index = s.startIndex
            for i in 1...str.count {
                index = s.index(after: index)
                let sub = s.substring(to: index)
                if wordSet.contains(sub) && wordBreak(s.substring(from: index), wordSet, &failedSet) {
                    return true
                }
            }
            
            failedSet.insert(s)
            return false
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.