LeetCode.140.单词拆分 II（困难）

题目

LeetCode.140.单词拆分 II（困难）

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

• 分隔时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

题解

如果知道s的末尾的字符组成的单词处在wordDict中，并且前面的子串也是可以被wordDict拆分，就可以把末尾的单词添加到句子中。

• s的末尾字符能不能组成wordDict中的单词，可以从末尾索引开始往前遍历一个个的试。
• 前面的子串是否可以被wordDict拆分，需要提前计算好，这里就借用 LeetCode.139.单词拆分（中等）中的状态表，即dp[i]：s的前i个字符组成的子串能否拆分成wordDict中的若干个单词。

用深度优先搜索递归试一遍就行，直到把s拆分完，结束搜索。

import java.util.*

class Solution {
    fun wordBreak(s: String, wordDict: List<String>): List<String> {
        val set = wordDict.toHashSet()
        val dp = getDpState(s, set)
        val result = mutableListOf<String>()
        dfs(s, set, s.length, result, dp, Stack())
        return result
    }

    /**
     * 获取一个一维数组，第i位表示，[s]的前i个字符组成的子串拆分成[wordDict]中的若干个单词
     */
    private fun getDpState(s: String, wordDict: Set<String>): Array<Boolean> {
        val n = s.length
        val state = Array(n + 1) { false }
        state[0] = true
        for (i in 1..n) {
            for (j in 0 until i) {
                val s2 = s.substring(j, i)
                if (state[j] && wordDict.contains(s2)) {
                    state[i] = true
                }
            }
        }
        return state
    }

    private fun dfs(s: String, wordDict: Set<String>, end: Int, result: MutableList<String>, dp: Array<Boolean>, path: Stack<String>) {
        // s[0:end-1]是否是单词，是的话，应当添加到路径中，同时是也是路径的终点，即递归树的叶子节点
        val prefix = s.substring(0, end)
        if (wordDict.contains(prefix)) {
            path.push(prefix)
            result.add(path.reversed().joinToString(" "))
            path.pop()
        }
        // 检索所有子串的拆分的可能组合
        for (i in 1..end) {
            // 前i个字符组成的左子串是可以被拆分为若干个单词的
            if (dp[i]) {
                // 就看右子串是否是单词
                val substring = s.substring(i, end)
                if (wordDict.contains(substring)) {
                    // 右子串是一个单词，应当添加到路径中
                    path.push(substring)
                    // 继续探寻左子串s[0:i-1]
                    dfs(s, wordDict, i, result, dp, path)
                    // 左子串探寻完了，从路径中移除当前单词，以不影响寻找下一个组合的单词路径
                    path.pop()
                }
            }
        }
    }
}