Word Break

Word-Break.java

/*
Give a string, and a dictionary, find out if this string could be segmented by a space which's substring 
are in this dictionary. 

For example, String "leetcode", dictionary ["leet", "code"], 
then return true, cause this string could be segmented as "leet code";
*/

public class Solution {
    public boolean wordBreak(String str, Set<String> dict) {
        // DP problem. 
        boolean[] array = new boolean[str.length()+1];
        array[0] = true; 
        
        for(int i = 0; i < str.length(); i++) { 
            StringBuffer tempString = new StringBuffer(str.substring(0, i+1));
            for(int j = 0; j <= i; j++) {
                if(array[j] && dict.contains(tempString.toString())) {
                    array[i+1] = true;
                    break;
                }
                tempString.deleteCharAt(0);
            }
        }
        return array[str.length()];
    }
}