By

Contents
  1. 1. 题目
  2. 2. 解题思路

题目

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

解题思路

先将wordDict根据首字母分类
然后先从s的第一个字母找起，有一个比s长一位的布尔数组，递归判断如果 最后一个是true，则代表能完全找到
这个布尔数据记录能找到匹配的最后一位
到达最后一个要结束，没有找到匹配的要结束，如果是true的要结束。
这道题算我动态规划自己做出来的第一道题。

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
45
46
47
48
49
50
class Solution {
        boolean[] exist;
        Map<Character,List<Integer>> map;
        List<String> wordDict;
        char[] sArray;
    public boolean wordBreak(String s, List<String> wordDict) {
        exist = new boolean[s.length()+1];
        map = new HashMap<Character,List<Integer>>();
        this.wordDict = wordDict;
        for(int i = 0 ; i< wordDict.size() ; i++){
            Character first =wordDict.get(i).charAt(0);
            if(!map.containsKey(first)){
                List list = new ArrayList<Integer>();
                list.add(i);
                map.put(first,list);
            }else{
                List<Integer> oldList = map.get(first);
                oldList.add(i);
            }
        }
        sArray =  s.toCharArray();
        innerCheck(0);
        return exist[s.length()];
    }
    public void innerCheck(int i){
        if(i == sArray.length){
            return;
        }
        char n = sArray[i];
        List<Integer> nList = map.get(n);
        if(nList == null){
            return;
        }
outer:
        for(Integer num: nList){
            String match = wordDict.get(num);
            char[] matchArray = match.toCharArray();
            for(int j = 0 ;j < matchArray.length ; j++){
                if(i+j >= sArray.length || sArray[i+j] != matchArray[j] ){
                    continue outer;
                }   
            }
            if(exist[i+matchArray.length]){
                return;
            }
            exist[i+matchArray.length] = true;
            innerCheck(i+matchArray.length);
        }
    }
}

动态规划还有点难掌握，需要多练习，现在的感觉是主要是能利用之前的状态。

Contents
  1. 1. 题目
  2. 2. 解题思路