139. Word Break

    /*
     * 139. Word Break
     * 12.31 by Mingyang
     * dp[i]表示从头开始到i结束的到底是不是满足条件
     */
         public boolean wordBreak(String s, Set<String> dict) {
                boolean[] dp = new boolean[s.length() + 1];
                dp[0] = true;
                for(int i=1; i <= s.length(); i++){
                    for(int j=0; j < i; j++){
                        if(dp[j] && dict.contains(s.substring(j, i))){
                            dp[i] = true;
                            break;
                        }
                    }
                }
                return dp[s.length()];
            }