leetcode139. 单词拆分-使用备忘录解决dfs超时带配图

leetcode139. 单词拆分-使用备忘录解决dfs超时带配图

六月 26, 2020

leetcode139. 单词拆分

给定一个非空字符串 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

dfs暴力

本题可以很简单的实现dfs的暴力解法。每次从字典里面选出来最后一个字符的下一个开头的string。比如匹配abcde，第一步可以选ab，下一步就需要选c开头的单词，然后遍历。
暴力的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashMap<Character,ArrayList<String>> map = new HashMap<>();
        for (String ss : wordDict) {
            ArrayList<String> list = map.getOrDefault(ss.charAt(0),new ArrayList<>());
            list.add(ss);
            map.put(ss.charAt(0),list);
        }
        //System.out.println(map);
        return dfs(s,new String(),map);
    }
    public boolean dfs(String s, String t, HashMap<Character,ArrayList<String>> map) {
        if (s.length() == t.length()) {
            if (s.equals(t)) return true;
            return false;
        }
        if (t.length() > s.length()) return false;
        ArrayList<String> list = map.get(s.charAt(t.length()));
        if (t.length() == 0) list = map.get(s.charAt(0));
        boolean flag = false;
        if (list == null) return flag;
        //遍历当前字母的所有单词
        for (int i = 0; i < list.size(); i++) {
            String out = list.get(i);
            if (out.length() + t.length() <= s.length()) {
                String m = s.substring(t.length(),out.length() + t.length());
                //这里substring多余了，因为递归终止条件就在判断是否相等
                if (m.equals(out)) {
                    flag = flag || dfs(s,t + out,map);
                }
                
            }
            
        }
        return flag;
    }
}

遇到这个用例就会超时

“aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab”
[“a”,”aa”,”aaa”,”aaaa”,”aaaaa”,”aaaaaa”,”aaaaaaa”,”aaaaaaaa”,”aaaaaaaaa”,”aaaaaaaaaa”]

先看这个过程中发生了什么。
见下图，小括号代表之前匹配过的。
在这里插入图片描述
可以看出在第二层就重复了。划红线的部分的子树，之后都是一样的，可以根据这个，构造一个备忘录，备忘录id就是之前构造的子串的长度。

dfs+备忘录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashMap<Character,ArrayList<String>> map = new HashMap<>();
        for (String ss : wordDict) {
            ArrayList<String> list = map.getOrDefault(ss.charAt(0),new ArrayList<>());
            list.add(ss);
            map.put(ss.charAt(0),list);
        }
        memo = new int[s.length()];
        //备忘录0表示没赋值过，1为true，-1为false，代表子树能不能构成目标字符串
        //System.out.println(map);
        return dfs(s,new String(),map);
    }
    public int[] memo;
    public boolean dfs(String s, String t, HashMap<Character,ArrayList<String>> map) {
        if (s.length() == t.length()) {
            if (s.equals(t)) return true;
            return false;
        }
        if (t.length() > s.length()) return false;
        ArrayList<String> list = map.get(s.charAt(t.length()));
        if (t.length() == 0) list = map.get(s.charAt(0));
        //备忘录里面已经有了
        if (memo[t.length()] == 1) return true;
        if (memo[t.length()] == -1) return false;
        
        boolean flag = false;
        if (list == null) return false;
        for (int i = 0; i < list.size(); i++) {
            String out = list.get(i);
            if (out.length() + t.length() <= s.length()) {
                String m = s.substring(t.length(),out.length() + t.length());
                if (m.equals(out)) {
                    boolean tf = dfs(s,t + out,map);
                    //添加到备忘录
                    memo[t.length()] = (tf ? 1 : -1);
                    flag = flag || tf;
                }
            }
            
        }
        return flag;
    }
}

题解区的动态规划想法也很好，但是这个我还真没想出来，这个dfs+备忘录的方式不比dp差，而且dp也是由这种方式转换过去的。
leetcode 114