leetcode139 word break 1- 单词拆解

快来打我* 2023-06-22 06:29 38阅读 0赞

通过函数递归调用判断是否包含：

class Solution {
        Set<String> set=new HashSet<>();
        public boolean wordBreak(String s, List<String> wordDict) {
            if(wordDict.contains(s))
                return true;
            if(set.contains(s))
                return false;
            for(String string:wordDict){
                if(s.startsWith(string)){
                    if(wordBreak(s.substring(string.length()),wordDict))
                        return true;
                }
            }
            set.add(s);
            return false;
        }
    }

动态规划解法：

1. 这题很好理解，意思就是给定一个字符串和一组字符串，如果该字符串能分成数组字符串里面的子字符串，那么就返回 true ,反之就返回 false;

2. 对于此类问题，我们应该条件反射的想到用动态规划来求解

3. 设置一个数组用 dp\[\] 来存储每个阶段的状态，其中 dp\[i\] 表示 0~i 个字符串可以拆分

4. 在第二层循环中，将当前字符串分成 0~j 和 j~i ,并判断当前字符串是否包含在其中

解题思路：

以字符串goodtecher字符串(长度为10)为例，wordDict： “good”， “techer”

满足isWordBreak\[4\]=true&&  wordDict.contains(s.subString(4,10)) ==true的前提下这会得到isWordBreak\[10\] =true;

状态转移方程式如下：

满足isWordBreak\[j\]=true的前提，wordDict.contains(s.subString(j,i)== true, \{0<=j<i<len+1\} 的话，isWordBreak\[i\] =true;

in the end，最后返回，isWordBreak\[s.length()\] 即可。

【注意点： （1）初始化isWordBreak长度为len+1 ，   （2） 初始化isWordBreak\[0\]=true,  （3） i遍历的范围，0<=i<len+1（4） 最后返回是sWordBreak\[s.length()\] 】

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdtYXg1NDIxMjAwOA_size_16_color_FFFFFF_t_70][]

动态规划视频参考：[https://www.youtube.com/watch?v=YxtQUbKbdUs][https_www.youtube.com_watch_v_YxtQUbKbdUs]

代码如下：

public boolean wordBreak(String s, Set<String> dict) {
            int len = s.length();
            boolean [] dp = new boolean[len + 1];
            dp[0] = true;
    
        //  当前字符串：0~i 
            for(int i = 1; i <= len; i++){
        
        // 将当前的字符串再进行拆分，查看它是否包含在 dict 中
                for(int j = 0; j < i; j++){
        
                // dp[j] 是前面已经计算出来的结果
                    if(dp[j] && dict.contains(s.substring(j,i))){
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[len];
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdtYXg1NDIxMjAwOA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019121422535167.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdtYXg1NDIxMjAwOA==,size_16,color_FFFFFF,t_70
[https_www.youtube.com_watch_v_YxtQUbKbdUs]: https://www.youtube.com/watch?v=YxtQUbKbdUs