首页 > 其他 > 详细

139. 单词拆分

时间:2021-07-20 23:03:38      阅读:25      评论:0      收藏:0      [点我收藏+]
package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class demo_139 {
    public boolean wordBreak(String s, List<String> wordDict) {
        //动态规划,表示字符串前i个子串能否被拆解
        boolean[] dp=new boolean[s.length()+1];
        HashSet<String> hashSet=new HashSet<String>(wordDict);
        dp[0]=true;
        for(int i=1;i<=s.length();i++) {
            for(int j=0;j<i;j++) {
                //当前子串能否被拆解为两个分开的子串
                if(dp[j]&&hashSet.contains(s.substring(j, i))) {
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        demo_139 d139=new demo_139();
        String s="cars";
        List<String> list=new ArrayList<String>();
        list.add("car");
        list.add("ca");
        list.add("rs");
        System.out.println(d139.wordBreak(s, list));
    }

}

 

139. 单词拆分

原文:https://www.cnblogs.com/Yshun/p/15037143.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!