Java Backtracking


  • 0
    G
    public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> rst = new ArrayList<String>();
    	if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) { return rst; }
    	int len = s.length(), i, j, k;
    	
    	// record the breakability.
        boolean[][] f = new boolean[len+1][len+1]; // f[i][j] = wordBreak(s.substring(i, j), wordDict);
        boolean[][] y = new boolean[len+1][len+1]; // y[i][j] = wordDict.contains(s.substring(i,j));
        f[len][len] = y[len][len] = true;
        for (i = 0; i < len; i++) { // start        	
        	for (j = i; j <= len; j++) { //end
        		y[i][j] = wordDict.contains(s.substring(i,j));
        		f[i][j] = y[i][j];
        	}
        }
        for (i = 0; i < len; i++) { // start
        	for (j = i+1; j <= len; j++) { //end
        		for (k = i+1; k < j; k++) { //divide
        			f[i][j] = f[i][j] || (f[i][k] && f[k][j]);
        		}
        	}
        }
        
        // backtraking
        backtrack(rst, s, f, y, new StringBuilder(), 0, len);
        return rst;
    }
    
    private List<String> backtrack(List<String> rst, String s, boolean[][] f, boolean[][] y, StringBuilder sb, int start, int end) {
    	if (!f[start][end]) {
    		return rst;
    	}
    	if (start == end) {
    		rst.add(sb.toString().trim());
    		sb = new StringBuilder();
    		return rst;
    	}
    	if (start + 1 == end) {
    		if (y[start][end]) {
    			sb.append(s.substring(start, end));
    			rst.add(sb.toString());
    			sb = new StringBuilder();
    			return rst;
    		}
    	}
    	for (int i = start+1; i <= end; i++) {
        	if (i < end && !(y[start][i] && f[i][end])) { 
        		continue; 
        	}
        	if (i == end && !y[start][i]) { 
        		continue; 
        	}
        	sb.append(s.substring(start, i) + " ");
        	backtrack(rst, s, f, y, sb, i, end);
        	int lastBlank = sb.lastIndexOf(" "), secLastBlank = sb.substring(0, lastBlank).lastIndexOf(" ");
        	sb.delete(secLastBlank+1, sb.length());
        	System.out.println("sb:" + sb.toString());
        }
    	return rst;
    }
    

    }


Log in to reply
 

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