2014年5月6日星期二

Dynamic Programing - Word Search

Dynamic programing question… need to think that way… it is a technique/skill

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        if(s == null || dict == null){
            return false;
        }
        int length = s.length();
        boolean[] process = new boolean[length+1]; //use bits if space is critical.
        process[length] = true;
        for(int i = length - 1; i >= 0; i--){
            for(int j = i + 1; j < length + 1; j++){
                if(dict.contains(s.substring(i, j)) && process[j] == true){
                    process[i] = true;
                    break;
                }
            }
        }
        return process[0];
    }
}

没有评论: