题目介绍

LeetCode 139. Word Break，原题的意思给定一个非空的字符串和非空的单词字典（不包含重复元素），判断字符串是否可以被分割成字典中的一个或者多个单词。

这题有进阶的题目，题解 Word Break II。

解题思路

这是一题典型的动态规划，如果一个单词存在一种分解方法，分解后每一单词都应该在字典中，那必定满足一个条件：对于该单词的最后一个分割点，分割点到单词末尾的字符串是一个单词，而这个分割点到单词开头所组成的字符串也是可分解的。所以只要验证满足这个条件，我们则可以确定字符串是可分解的。

用外层循环来控制待验证的字符串的长度，而用内层的循环来寻找这么一个分割点，可以把字符串分成一个单词和一个同样可分解的子字符串。
同时，我们用数组记录下字符串长度递增时可分解的情况，以供之后使用，避免重复计算。用 Bool wordArray[i] 表示到字符串 s 的第 i 个字符时，是否可以用 wordDict 中的单词来表示。
假设有 wordArray[0…i-1] 的结果，那么 wordArray[i] 的值应该是：wordArray[i] = wordArray[j] && s.substring(j, i) in wordDict，其中 j 属于[0…i-1]。

时间复杂度 O(n²)，空间复杂度 O(n)。

class Solution {
    func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {

        if s.isEmpty {
            return true
        }

        if wordDict.count == 0 {
            return false
        }

        var wordArray = Array.init(repeating: false, count: s.count + 1)
        wordArray[0] = true

        for i in 1...s.count {
            for j in stride(from: i-1, through: 0, by: -1) {

                if wordArray[j] && wordDict.contains(String(s[s.index(s.startIndex, offsetBy: j)..<s.index(s.startIndex, offsetBy: i)])) {
                    wordArray[i] = true
                    break
                }
            }
        }

        return wordArray[s.count]
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2017/10/14/WordBreak/