当前位置:   article > 正文

动态规划 回溯 记忆化回溯 139.单词拆分

记忆化回溯

在这里插入图片描述

动态规划题解:

:dp[s.length],dp长度是n+1,存放boolean
1)定义dp数组:dp[i]:长度为 i 的 s[0:i-1] 子串是否能拆分成单词,是一个 Boolean 值。
2)初始化及basecase:初始化 dp[0]=True 空字符可以被表示
3)状态转移:
s[0:i] 子串的 dp[i+1] 是否为真(是否可拆分成单词),取决于两点:
它的前缀子串 s[0:j-1] 的 dp[j] ,是否为真。
剩余子串 s[j:i],是否是一个独立的单词。
在这里插入图片描述

solution:

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n=s.length();
        boolean[] dp=new boolean[n+1];
        dp[0]=true;
        for(int i=1;i<=n;i++){
           for(int j=0;j<i;j++){
               if(dp[j]&&wordDict.contains(s.substring(j,i))){
                   dp[i]=true;
                   break;// i长度的子串已经可以break成单词了,不需要j继续划分子串了
               }
           }
        }
       return dp[n];
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

回溯题解:

将字典加入到set中,逐渐增加字符直到匹配到set中的单词,再递归判断剩下的字符串,无法匹配返回false,最后剩下空则说明全部匹配。subString生成了新的字符串对象,因此不会对原来的字符串产生影响

substring(i)返回值是 str的索引位置i,到最大索引(两个索引都包括)

超时

class Solution {
    public boolean backtrack(String s, Set<String> set) {
        if (s.length() == 0) return true;
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.substring(0, i + 1))){
                if (backtrack(s.substring(i + 1), set)) return true;
            }
        }
        return false;
    }
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        return backtrack(s, set);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

记忆化回溯题解:

增加一个boolean数组表示当前位置之后的字符串是否遍历过了
如果遍历过了并且没有提前递归的返回true说明这个位置后面的匹配是不会成功的,因此直接返回false

class Solution {
    boolean[] mem;
    public boolean backtrack(String s, int start, Set<String> set) {
        if (s.length() == 0) return true;
        if (mem[start]) return false;
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.substring(0, i + 1))){
                if (backtrack(s.substring(i + 1), start + i + 1, set)) return true;
            }
        }
        mem[start] = true;
        return false;
    }
    public boolean wordBreak(String s, List<String> wordDict) {
        this.mem = new boolean[s.length()];
        Set<String> set = new HashSet<>(wordDict);
        return backtrack(s, 0, set);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/天景科技苑/article/detail/1003348
推荐阅读
相关标签
  

闽ICP备14008679号