Palindrome Partitioning

Leetcode 131.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public List<List<String>> partition(String s) {     
      List<String> list = new ArrayList<>();
      List<List<String>> ans = new ArrayList<>();
       backtricking(list,s,ans); 
      return ans;
    }
    public void backtricking(List<String> list, String s,List<List<String>> ans){
     //recursion stop condition 
     if(s.length() == 0){
      //collect the results  
      ans.add(new ArrayList<>(list));   
      return;
     }  

     //for loop for this layer 
     for(int i = 0; i < s.length();i++){
        //process the nodes 
      if(isPalindrome(s,0,i)){       
        list.add(s.substring(0,i+1));
        //recursion 
        backtricking(list,s.substring(i+1),ans);
        //undo the previous operations
        list.remove(list.size() - 1);
      }
     }

    }
    public boolean isPalindrome(String s,int start,int end){ 
      while(start < end){
          if(s.charAt(start++) != s.charAt(end--))
            return false;
      }
      return true;   
    }
}