日练算法-单词拆分

1 题目 1.1 题目描述

给你一个字符串 str 和一个字符串列表 wordDict 作为字典。
请你判断是否可以利用字典中出现的单词拼接出 str 。

原题链接：https://leetcode-cn.com/problems/word-break/

解题注意：

1.拆分时可以重复使用字典中的单词，可以假设字典中没有重复的单词；
2.不要求字典中出现的单词都被使用

示例

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。

注意，你可以重复使用字典中的单词

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

1.2 题目分析及解答 解题思路1-遍历

解答该题同样可以使用暴力的遍历方式，只是这两种遍历较之前有些变化。如下：

1.深度优先遍历搜索(DFS)
2.广度优先遍历搜索(BFS)

DFS方法

首先，针对深度遍历搜索方法，其定义为：是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索（百度百科）。具体思路如下图：

思路：每次截取一个子串，判断他是否存在于字典中，如果不存在于字典中，继续截取更长的子串……如果存在于字典中，然后递归拆分剩下的子串，这是一个递归的过程。上面的执行过程我们可以把它看做是一棵n叉树的DFS遍历

package list;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;


public class IDEA_1 {

    public static void main(String[] args){
        //数组可以随机定义，此处选取LeetCode数据
        String str = "leetcode";
        List wordDict = Arrays.asList("leet", "code");
        System.out.println("单词拆分结果："+ wordBreak(str,wordDict));

    }


    public static boolean wordBreak(String s, List wordDict) {
        return dfs(s, wordDict, new HashSet<>(), 0);
    }

    //start表示的是从字符串s的哪个位置开始
    public static boolean dfs(String s, List wordDict, Set indexSet, int start) {
        //字符串都拆分完了，返回true
        if (start == s.length())
            return true;
        for (int i = start + 1; i <= s.length(); i++) {
            //如果已经判断过了，就直接跳过，防止重复判断
            if (indexSet.contains(i))
                continue;
            //截取子串，判断是否是在字典中
            if (wordDict.contains(s.substring(start, i))) {
                if (dfs(s, wordDict, indexSet, i))
                    return true;
                //标记为已判断过
                indexSet.add(i);
            }
        }
        return false;
    }
}

BFS

对于BFS遍历算法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。如下图

BFS算法只需要使用一个队列记录每一层需要记录的值即可。BFS中在截取的时候，如果截取的子串存在于字典中，我们就要记录截取的位置，到下一层的时候就从这个位置的下一个继续截取，代码如下：

package list;
import java.util.*;


public class IDEA_2 {

    public static void main(String[] args){
        //数组可以随机定义，此处选取LeetCode数据
        String str = "leetcode";
        List wordDict = Arrays.asList("leet", "code");
        System.out.println("单词拆分结果："+ wordBreak(str,wordDict));

    }

    public static boolean wordBreak(String s, List wordDict) {
        //这里为了提高效率，把list转化为set，因为set的查找效率要比list高
        Set setDict = new HashSet<>(wordDict);
        //记录当前层开始遍历字符串s的位置
        Queue queue = new LinkedList<>();
        queue.add(0);
        int length = s.length();
        //记录访问过的位置，减少重复判断
        boolean[] visited = new boolean[length];
        while (!queue.isEmpty()) {
            int index = queue.poll();
            //如果字符串都遍历完了，直接返回true
            if (index == length)
                return true;
            //如果被访问过，则跳过
            if (visited[index])
                continue;
            //标记为访问过
            visited[index] = true;
            for (int i = index + 1; i <= length; i++) {
                if (setDict.contains(s.substring(index, i))) {
                    queue.add(i);
                }
            }
        }
        return false;
    }
}

以上两种方法可以解决问题，但是执行效率较低，leetcode和牛客等网站编译不易通过。

​

解题思路2-动态规划

1、确定dp数组以及下标的含义——这里dp[i]：
    字符串长度为i，dp[i]=true表示可以拆分为一个或多个在字典中出现的单词
2、确定递推公式，if(dp[j]=true && set.contains(s.substring(j,i))，才会出现dp[i]=true
3、dp数组初始化,dp[0]=true
4、确定遍历顺序，双层for循环遍历，i从0到s.length（遍历所有字符串长度），j从长度0到i
5、举例推导dp数组
6、最后返回dp[s.length()]

我们定义dp[i]表示字符串的前i个字符经过拆分是否都存在于字典wordDict中。如果要求dp[i]，我们需要往前截取k个字符，判断子串[i-k+1，i]是否存在于字典wordDict中，并且前面[0，i-k]子串拆分的子串也是否都存在于wordDict中，如下图所示：

前面 [0，i-k] 子串拆分的子串是否都存在于 wordDict 中只需要判断 dp[i-k] 即可，而子串 [i-k+1，i] 是否存在于字典 wordDict 中需要查找，所以动态规划的递推公式很容易列出来

dp[i]=dp[i-k]&&dict.contains(s.substring(i-k, i));

package list;
import java.util.Arrays;
import java.util.List;

public class IDEA_3 {

    public static void main(String[] args){
        //数组可以随机定义，此处选取LeetCode数据
        String str = "leetcode";
        List wordDict = Arrays.asList("leet", "code");
        System.out.println("单词拆分结果："+ wordBreak(str,wordDict));

    }
    
     /**
        1.定义：boolean dp[i] -> 用字典中的单词能否前i个字符串
        2.递推公式：
            i > j
            如果前j个字符串能够用字典中的词汇拼出(这是前提) 
            && 
            从j到i这段字符串能够在字典中找到 -> 说明前i个字符串能够用字典中的词汇拼出
            if(dp[j] == true && wordDict.contains(s.substring(j,i))) -> dp[i] = true 
        3.初始化：
            dp[0] = true 空字符串不用字典中的词汇也能拼出 无为而治 同时之后的结果也是以dp[0]为基础 如果为false
            之后的结果也都会为false
        4.遍历顺序：
            这道题理论上先遍历字符串(背包)还是先遍历字典(物品)的结果都是一样的
            只不过因为涉及到子串问题的特殊性 单词的顺序会进行打乱 不会按照字典中的顺序出现
            因此为了方便可以使用先遍历背包再遍历物品的方式
            如果反过来的话 需要先用容器将物品进行存储 较为麻烦
     */

    public static boolean wordBreak(String s, List dict) {
        boolean[] dp = new boolean[s.length() + 1];
        for (int i = 1; i <= s.length(); i++) {
            //枚举k的值
            for (int k = 0; k <= i; k++) {
                //如果往前截取全部字符串，我们直接判断子串[0,i-1]
                //是否存在于字典wordDict中即可
                if (k == i) {
                    if (dict.contains(s.substring(0, i))) {
                        dp[i] = true;
                        continue;
                    }
                }
                //递推公式
                dp[i] = dp[i - k] && dict.contains(s.substring(i - k, i));
                //如果dp[i]为true，说明前i个字符串结果拆解可以让他的所有子串
                //都存在于字典wordDict中，直接终止内层循环，不用再计算dp[i]了。
                if (dp[i]) {
                    break;
                }
            }
        }
        return dp[s.length()];
    }

}

正在上传…重新上传取消

优化： 将 wordDict 构建为一个 Set 能提高 contains 方法的匹配效率，于是：

package list;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;


public class IDEA_4 {

    public static void main(String[] args){
        //数组可以随机定义，此处选取LeetCode数据
        String str = "leetcode";
        List wordDict = Arrays.asList("leet", "code");
        System.out.println("单词拆分结果："+ wordBreak(str,wordDict));

    }

    public static boolean wordBreak(String s, List wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        //优化之处
        Set set = new HashSet<>(wordDict);
        for (int r = 1; r < s.length() + 1; r++) {
            for (int l = 0; l < r; l++) {
                if (dp[l] == true && set.contains(s.substring(l, r))) {
                    dp[r] = true;
                }
            }
        }
        return dp[s.length()];
    }

还有大佬优化的方法，此处给出代码逻辑，供大家思考：

public boolean wordBreak(String s, List wordDict) {
    //转化为是否可以用 wordDict 中的词组合成 s，完全背包问题
    //有顺序的完全背包问题，先遍历target，再遍历背包
    //dp[i]表示：字符串的前i个字符是否可以由背包中的单词组成
    int len = s.length();
    boolean[] dp = new boolean[len + 1];
    //初始化d
    dp[0] = true;
    // 如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
    // 所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

    //这里从1开始遍历是因为substring左开右闭
    for(int i = 1; i <= len; i++){
        //倒着遍历，考虑到单词长度可能远小于target长度，倒着遍历效率更高
        for(int j = i - 1; j >= 0; j--){
            //如果dp[j]为false，已经不符合题意了，继续下一个比较
            if(dp[j] == false) continue;
            if(wordDict.contains(s.substring(j, i)) && dp[j]){
                //如果为true，则必定为true，直接break
                dp[i] = true;
                break;
            }
                
        } 

    }
    return dp[len];
}

    ​    ​

参考：

1.https://leetcode-cn.com/problems/word-break/