动态规划五：单词拆分-一一网

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

一、题目单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

示例：

输入: s = “leetcode”, wordDict = [“leet”, “code”]

输出: true

解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

二、分析

如果字符串s能被拆分为多个单词，则一定存在j使得 s.substring(j) 和 s.substring(j,slen+1)两个子串都能被拆分为多个单词。同理，两个子串也存在于字符串s相同的性质。则我们可以从0遍历 s.length()，记录每个位置之前的子串是否能够被拆分为多个单词。

确定dp数组及下标含义

dp[i]: s.substring(i) 能否被拆分为单词。注：dp[i] 记录的应该是字符串下标为 i-1 的位置可否能拆分为多个单词的情况。

确定递推公式

对于dp[i]，如果 s.substring(i) 能被拆分为多个单词，则一定存在j使得 s.substring(j) 子串能被拆分为多个单词，以及 s.substring(j,i) 子串为一个单词。所以有，dp[i] = dp[j] && wordDict.contains(s.substring(j,i))。

dp数组初始化

dp[0]代表的是空子串的情况，题目中指出，给定一个非空字符串，所以空子串在本题中应该是无意义的。但是，dp[i]需要依靠dp[j]确定，如果dp[0]为false，则后面dp[i]是否为true都将无意义，所以dp[0]必须为true。

遍历顺序

本题使用两层循环遍历，外层循环自然是从0遍历到s.length()。对于内层，从i遍历到1能明显减少循环次数。

举例推导dp数组

三、代码实现

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int sLength = s.length();
        boolean[] dp = new boolean[sLength+1];
        dp[0] = true;
        for(int i = 1; i <= sLength; i++){
            for (int j = i; j >= 0; j--){
                if(dp[j] && wordSet.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[sLength];
    }
}
复制代码

四、进阶

140.单词拆分II

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {

    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int len = s.length();

        // 第 1 步：动态规划计算是否有解
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;

        for (int right = 1; right <= len; right++) {
            // 从后向前遍历是更快的
            for (int left = right - 1; left >= 0; left--) {
                if (wordSet.contains(s.substring(left, right)) && dp[left]) {
                    dp[right] = true;
                    break;
                }
            }
        }

        // 第 2 步：回溯算法搜索所有符合条件的解
        List<String> res = new ArrayList<>();
        if (dp[len]) {
            Deque<String> path = new ArrayDeque<>();
            dfs(s, len, wordSet, dp, path, res);
            return res;
        }
        return res;
    }

    /**
     * s[0:len) 如果可以拆分成 wordSet 中的单词，把递归求解的结果加入 res 中
     *
     * @param s
     * @param len     长度为 len 的 s 的前缀子串
     * @param wordSet 单词集合，已经加入哈希表
     * @param dp      预处理得到的 dp 数组
     * @param path    从叶子结点到根结点的路径
     * @param res     保存所有结果的变量
     */
    private void dfs(String s, int len, Set<String> wordSet, boolean[] dp, Deque<String> path, List<String> res) {
        if (len == 0) {
            res.add(String.join(" ",path));
            return;
        }

        // 可以拆分的左边界从 len - 1 依次枚举到 0
        for (int i = len - 1; i >= 0; i--) {
            String suffix = s.substring(i, len);
            if (wordSet.contains(suffix) && dp[i]) {
                path.addFirst(suffix);
                dfs(s, i, wordSet, dp, path, res);
                path.removeFirst();
            }
        }
    }
}
复制代码