Word Break II

题目介绍

LeetCode 140. Word Break II，题目的意思原题的意思给定一个非空的字符串和非空的单词字典（不包含重复元素），将所有可能的分割方式用数组输出。

解题思路

记忆化搜索，在搜索过程中，使用字典tokenDict将已经搜索过的子句的拆解方案记录下来，从而实现DFS的剪枝。

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

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.count == 0 {
            return [""]
        }

        if let value = cache[s] {
            return value
        }

        var result = [String]()

        for word in wordDict {
            if s.hasPrefix(word) {
                let subWordBreaks = DFS(String(s.suffix(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;
    }
}

**版权声明**

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/15/WordBreakII/