139. 单词拆分

1.解题思路:

  • 动态规划听上去非常高大上,但是其实都是源自于一个很自然的想法,就拿这道题来说,假如需要判断”onetwothreefour”这一个字符串能不能满足条件,我们很自然的想法就是:
  • 如果”onetwothree”这一段可以拆分,再加上four如果也可以,那不就行了;
  • 或者
  • 如果”onetwothre”这一段可以拆分,再加上efour如果也可以,那不就行了;
  • 这其实已经抓住了动态规划的最核心的东西了,换成式子来表达,就是
1
2
dp["onetwothreefour"] = dp["onetwothree"这一段] && 判断一下"four"
dp["onetwothreefour"] = dp["onetwothre"这一段] && 判断一下"efour"

2.代码:

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
import java.util.*;

public class 单词拆分_139 {
public static void main(String[] args) {
}
public Map<String, Boolean> map = new HashMap<>();
public boolean wordBreak(String s, List<String> wordDict){

boolean[] dp = new boolean[s.length() + 1];
//Java boolean数组默认值为False

//将List中单词放进 HashMap
for(String word:wordDict){
map.put(word, true);
}

//初始化
dp[0] = true;

//遍历
/*
* public String substring(int beginIndex, int endIndex)
* beginIndex -- 起始索引(包括), 索引从 0 开始
* endIndex -- 结束索引(不包括)
* 索引:读取数组时的下标
* */
for(int i=1;i<s.length();i++){
for(int j=i-1;j>=0;j--){
dp[i] = dp[j] && check(s.substring(j, i));
if(dp[i]) break;//这句也很精髓
}
}
return dp[s.length()];
}
public boolean check(String s){
return map.getOrDefault(s, false);
}
}

3.Refrence