leetcode/code/lc139.java at master · mJackie/leetcode · GitHub

39 lines (37 loc) · 1.29 KB

package code;

* 139. Word Break

* 题意：是否能够分词

* 难度：Medium

* 分类：Dynamic Programming

* 思路：动态规划

* Tips：巧妙的方法，防止了复杂的操作，通过遍历之前计算出来的结果

* 递归的方法本质和dp是一样的，记住用备忘录算法，把之前的结果记下来

* lc140

import java.util.HashMap;

import java.util.List;

public class lc139 {

public boolean wordBreak(String s, List<String> wordDict) {

boolean[] dp = new boolean[s.length()+1];

dp[0] = true;

for (int i = 1; i < dp.length ; i++) {

for (int j = 0; j < i ; j++) { //遍历之前计算出来的结果

if( dp[j]==true && wordDict.contains(s.substring(j,i)))

dp[i] = true;

}

return dp[s.length()];

}

HashMap<String, Boolean> hm = new HashMap();

public boolean wordBreak2(String s, List<String> wordDict) {

if(hm.containsKey(s)) return hm.get(s);

if(s.length() == 0) return true;

Boolean flag = false;

for(String word:wordDict){

if(s.startsWith(word)) flag = flag||wordBreak(s.substring(word.length()), wordDict); //注意函数 startsWith

}

hm.put(s, flag);

return flag;

}

Expand file tree