*Java* 3ms recursive solution with DP (but not so clean)


  • 0
    E

    It is far from perfect or even good, so ignore this solution if you think the coding is too long.

    public boolean wordBreak(String s, Set<String> wordDict) {
    	int min=s.length(), 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;
    	}
    	return wordBreak(min, max, s, wordDict, s.length(), 0, s.length(), new int[s.length()+1][s.length()+1]);
    }
    
    private boolean wordBreak(int min, int max, String s, Set<String> wordDict, int L, int start, int end, int[][] contains) {
    	if(contains[start][end]!=0) return contains[start][end]==1 ? true : false;
    	if(start==L) return true;
    	int locMax = start+max < L ? start+max : L;
    	for(int j=start+min; j<=locMax; j++) {
    	    if(contains[start][j]!=-1) {
            	if(wordDict.contains(s.substring(start,j))) {
            		contains[start][j] = 1;
            		if(wordBreak(min, max, s, wordDict, L, j, L, contains)) {
            			contains[j][L] = 1;
    	        		return true;
            		}
            		contains[j][L] = -1;
            	}
            	else contains[start][j] = 1;
    	    }
    	}
    	contains[start][end] = -1;
    	return false;
    }

Log in to reply
 

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