DFS和BFS时的补救方法

题目：https://leetcode.cn/problems/word-break/description/?favorite=2cktkvj

139. 单词拆分

中等

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

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

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

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

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

 参考：参考链接

KEY：单纯使用DFS发现大部分通过了，但是部分样例超时了

1.  
   public class Solution {
2.  
   String s;
3.  
   List<String> wordDict;
4.  
   int n;
5.  
   boolean res = false;
6.  
   public boolean wordBreak(String s, List<String> wordDict) {
7.  
   this.s = s;
8.  
   this.wordDict = wordDict;
9.  
   n = s.length();
10.  
    for(int i=0;i<n;i )
11.  
    {
12.  
    dfs(0,i);
13.  
    }
14.  
    return res;
15.  
    }
16.  
    void dfs(int start,int end)
17.  
    {
18.  
    //[start,end]期间是否可以作为一个单词
19.  
    String subString = s.substring(start,end 1);
20.  
    if(wordDict.contains(subString))
21.  
    {
22.  
    if(end == n-1)
23.  
    {
24.  
    //结束了
25.  
    res = true;
26.  
    return;
27.  
    }
28.  
    for(int i=end 1;i<n;i )
29.  
    dfs(end 1,i);
30.  
    }
31.  
    }
32.  
     
33.  
    public static void main(String[] args) {
34.  
    Solution s = new Solution();
35.  
    System.out.println(s.wordBreak("leetcode", Arrays.asList("leet","code")));
36.  
     
37.  
    }
38.  
    }

直接用记忆化搜索补救！

加入dp[][]//进行缓存

1.  
   public class Solution {
2.  
   int[][] dp;
3.  
   String s;
4.  
   List<String> wordDict;
5.  
   int n;
6.  
   boolean res = false;
7.  
   public boolean wordBreak(String s, List<String> wordDict) {
8.  
   this.s = s;
9.  
   this.wordDict = wordDict;
10.  
    this.dp = new int[n 1][n 1];//1->true,0->null,-1->false
11.  
    Arrays.fill(dp,0);
12.  
    n = s.length();
13.  
    for(int i=0;i<n;i )
14.  
    {
15.  
    dfs(0,i);
16.  
    }
17.  
    return res;
18.  
    }
19.  
    void dfs(int start,int end)
20.  
    {
21.  
    //[start,end]期间是否可以作为一个单词
22.  
    String subString = s.substring(start,end 1);
23.  
    if(wordDict.contains(subString))
24.  
    {
25.  
    dp[start][end] = 1;
26.  
    if(end == n-1)
27.  
    {
28.  
    //结束了
29.  
    res = true;
30.  
    return;
31.  
    }
32.  
    for(int i=end 1;i<n;i )
33.  
    {
34.  
    if(dp[end 1,n-1] == 1)
35.  
     
36.  
    dfs(end 1,i);
37.  
    }
38.  
     
39.  
    }
40.  
    dp[start][end] =-1;
41.  
    }
42.  
     
43.  
    public static void main(String[] args) {
44.  
    Solution s = new Solution();
45.  
    System.out.println(s.wordBreak("leetcode", Arrays.asList("leet","code")));
46.  
     
47.  
    }
48.  
    }

这篇好文章是转载于：学新通技术网