6. ＜ tag backtracking and cutting problems ＞ lt.131 Split palindrome string

lt.131. Split palindrome string

[ Case needs ]

[ Thought analysis ]

[ Code implementation ]

class Solution {
    
    List<List<String>> lists = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
    
        //
        backTracking(s, 0);
        return lists;

    }


    //1.  Recursive function : String cutting , 
    public void backTracking(String s, int startIndex){
    
        //2.  The end condition 
        //startIndex  Is the cutting line 
        if(startIndex >= s.length()){
    
            lists.add(new ArrayList<>(path));
            return;
        }

        //3.  Single layer recursive logic 
        for(int i = startIndex; i < s.length(); i++){
    
            if(isParlindrome(s, startIndex, i)){
    
                
                String str = s.substring(startIndex, i + 1);
                path.add(str);
            }else{
    
                continue;
            }

            backTracking(s, i + 1);

            path.remove(path.size() - 1);
        }
    }

    public boolean isParlindrome(String s, int left, int right){
    
        while(left < right){
    
            if(s.charAt(left) != s.charAt(right)){
    
                return false;
            }else{
    
                ++left;
                --right;
            }
        }

        return true;
    }
}