LeetCode 140. Word Break II [Swift 题解]

题目

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.
Example 1:

Input:  
s = "catsanddog"  
wordDict = ["cat", "cats", "and", "sand", "dog"]  
Output:  
[
  "cats and dog",
  "cat sand dog"
]

附: 原题目链接

思路

一种比较直观的解法是recursive的解法。 把原string分成左右两部分substring, 如果右边的string在word list里,然后可以对左边的string recursively的求解。

class Solution {  
    var memo = [String: [String]]()

    func wordBreak(_ s: String, _ wordDict: [String]) -> [String] {
        var words = Set<String>()
        for word in wordDict {
            words.insert(word)
        }

        return wordBreak(s, words)
    }

    func wordBreak(_ s: String, _ words: Set<String>) -> [String] {
        if let result = memo[s] {
            return result
        }

        var result = [String]()
        for offset in 0..<s.count {
            let index = s.index(s.startIndex, offsetBy: offset)
            let left = String(s[s.startIndex..<index])
            let right = String(s[index..<s.endIndex])
            if words.contains(right) {
                if left.isEmpty {
                    result.append(right)
                } else {
                    let intermediate = wordBreak(left, words)
                    for word in intermediate {
                        let one = "\(word) \(right)"
                        result.append(one)
                    }
                }
            }
        }

        memo[s] = result

        return result
    }
}

另外一种解法就是动态规划(DP)解法

//TODO
...

chenbo

编程爱好者

Singapore