easy understanding Java Backtracking


  • 0
    R
    public List<List<String>> partition (String s) {
    		List<List<String>> ans = new ArrayList<>();	
    		helper(ans, new ArrayList<>(), s, 0, 1);
    		return ans;
    	}
    	
    // backtracking to put every tmp into and
    public void helper (List<List<String>> ans, List<String> tmp, String s, int start, int end) {
    	if (end == s.length() + 1) {
    		ans.add( new ArrayList(tmp) );
    	} else {
    		for (int i = end; i <= s.length(); i++) {
    			if ( check (s.substring(start, i) ) ) {
    				tmp.add(s.substring(start, i) );
    				helper(ans, tmp, s, i, i + 1);
    				tmp.remove(tmp.size() - 1);
    			}
    		}
    	}	
    }
    
    // to check if substring is palindrome
    public boolean check(String s) {
    	for (int i = 0; i < s.length() / 2; i++) 
    		if ( s.charAt(i) != s.charAt(s.length() - i - 1) )
    			return false;
    	return true;
    }
    
    

Log in to reply
 

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