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));
    }

}