Swift solution


  • 0
    class Solution {
        func wordBreak(_ s: String, _ wordDict: [String]) -> [String] {
            var cache = [String: [String]]()
            return DFS(s, wordDict, &cache)
        }
        
        func DFS(_ s: String, _ wordDict: [String], _ cache: inout [String: [String]]) -> [String] {
            if s.characters.count == 0 {
                return [""]
            }
            if let value = cache[s] {
                return value
            }
            
            var result = [String]()
            
            for word in wordDict {
                if s.hasPrefix(word) {
                    let subWordBreaks = DFS(s.substring(from: word.endIndex), wordDict, &cache)
                    for subWordBreak in subWordBreaks {
                        if subWordBreak.isEmpty {
                            result.append(word)
                        } else {
                            result.append(word + " " + subWordBreak)
                        }
                    }
                }
            }
            cache[s] = result;
            
            return result;
        }
    }
    

Log in to reply
 

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