Easy to understand neat and modular Java solution. Comments included.


  • 1
    P
    public  List<List<String>> partition(String s) {
    		List<List<String>> result = new ArrayList<>();
    		if (s.length() == 0)
    			return result;
    		DFS(s, 0, s.length() - 1, new ArrayList<>(), result);
    		return result;
    
    	}
    
    	private  void DFS(String str, int start, int end, List<String> list, List<List<String>> result) {
    		if (start > end) { // base case. When we reach the length of string basically.
    			result.add(new ArrayList<>(list));
    			return;
    		}
    		for (int i = start; i <= end; i++) {
    			if (isPalindrome(str.substring(start, i + 1))) { // only Palindromic substring taken to next level of recursion.
    				list.add(str.substring(start, i + 1));
    				DFS(str, i + 1, end, list, result);
    				list.remove(list.size() - 1); // Gotta remove what's been added to keep things going. 
    			}
    
    		}
    	}
    
    	private boolean isPalindrome(String str) { // usual Palindromic check method.
    		if (str.length() == 0)
    			return true;
    
    		for (int i = 0; i < str.length() / 2; i++) {
    			if (str.charAt(i) != str.charAt(str.length() - 1 - i))
    				return false;
    		}
    		return true;
    	}
    

  • 0
    C

    @piyush121 Hi. Thanks for sharing... just don't understand why this line works:

    list.remove(list.size() - 1); // Gotta remove what's been added to keep things going. 
    

    I tried to remove this line, and it returns duplicated results from the previous run. But in the code, looks like it only removes one element.


  • 1
    P

    @chenw2000 Thanks for the reply. So that line is very common in recursive functions. If you know recursion well then you can visualize the state of the list while recursion. We add an element to the list and send that list to the next level. When the recursive call returns back to this state we remove the last element we added because we already generated all the palindromes using that element. It's true that that line executes only once but that execution happens for every recursive call. I hope this makes sense if not please feel free to reply.


  • 0
    G

    Thanks for sharing! Great solution.

    Just have one question: de we really need the input parameter "end"? It seems "end" is always "s.length() - 1"


  • 0
    P

    @genius1wjc You're welcome.
    No, its not needed. But having end as a parameter is slightly faster as you don't have to call the length() method of the String in every recusrive step.


  • 0
    G

    @piyush121 Right, thanks


Log in to reply
 

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