My 3ms DP solution in Java


  • 0
    T
    public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        int len = s.length();
        boolean[] valid = new boolean[len+1];
        valid[0] = true;
        for(int i=1;i<=len;i++){
            for(int j=i-1;j>=0;j--){
                String cur = s.substring(j,i);
                if(wordDict.contains(cur)&&valid[j]){
                    valid[i] = true;//Look backward,break the loop immediately when a valid separation is found
                    break;
                }
            }
        }
        return valid[len];
    }
    

    }


  • 0
    E

    Very smart idea. I further modified it to skip unnecessary indices and saved 1ms :)

    public boolean wordBreak(String s, Set<String> wordDict) {
    	int len = s.length(), min=len, max = 0; // min & max length of words in wordDict
    	for(String str : wordDict) {
    		int L = str.length();
    		min = L < min ? L : min;
    		max = L > max ? L : max;
    	}
        boolean[] valid = new boolean[len+1];
        valid[0] = true;
        for(int i=1;i<=len;i++){
            for(int j=i-min;j>=i-max && j>=0;j--){
                String cur = s.substring(j,i);
                if(wordDict.contains(cur)&&valid[j]){
                    valid[i] = true;//Look backward,break the loop immediately when a valid separation is found
                    break;
                }
            }
        }
        return valid[len];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.