iframe-proxy | Sunbelt Computer Software

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;

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

lc139.java

Latest commit

History

lc139.java

File metadata and controls