131. Palindrome Partitioning (Backtracking) 20.3.25 Medium

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

Solution: ---------------------------- Backtracking --------------------------- https://www.youtube.com/watch?v=UFdSC_ml4TQ
------------------------------ Time complexity: O(n*(2^n))
------------------------------ For a string with length n, there will be (n - 1) intervals between chars.
------------------------------ For every interval, we can cut it or not cut it, so there will be 2^(n - 1) ways to partition the string.
------------------------------ partition the string. For every partition way, we need to check if it is palindrome, which is O(n).
------------------------------ So the time complexity is O(n*(2^n))
------------------------------ O(n) S
class Solution(object):                                        # This question asks us to find all possible answer,
                                                               # and backtracking is a very common solution for this kind of question
    def partition(self, s):
        self.res = []
        self.backtracking_help(s, [])
        return self.res
        """
        :type s: str
        :rtype: List[List[str]]
        """
    def backtracking_help(self, s, path):
        if not s:
            self.res.append(path[:])
            return
        for i in range(1, len(s) + 1):                        # Why here is len(s) + 1 instead of len(s) as usual
                                                              # Because, later, s[:i] is called and i is not included
                                                              # also i need to be len(s)
                                                              # in order to let s[i:] to be None and meet the base case: "if not s"
                                                              # to append path to res
            '''
            How to come up with this algorithm:
            create a i to loop over the s is the first step,
            for each section, we will check if this is a palindrome, if yes, we will call the recursion function to dig deeper,
            but now, we are not interested in s[:i] since it is already been investigated, so, we pass s[i:] into the next recursion
            and so on and so on
            这样做比我一开始的想法（分成左subarray和右subarray更好，因为the length of path is not 2 but uncertain）
            '''
            if self.isPali(s[:i]):                            
                self.backtracking_help(s[i:], path + [s[:i]])
        
    def isPali(self, s):
        return s == s[::-1]


Java Version:
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        backtracking(s, new ArrayList<>(), res);
        return res;
    }
    
    public void backtracking(String currS, List<String> path, List<List<String>> res) {
        if (currS.length() == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 1; i <= currS.length(); i ++) {
            if (checkPalin(currS.substring(0, i))) {
                path.add(currS.substring(0, i));
                backtracking(currS.substring(i, currS.length()), path, res);
                path.remove(path.size() - 1);
            }
        }
    }
    
    public boolean checkPalin(String s) {
        int left = 0, right = s.length() - 1;
        while (left <= right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left ++;
            right --;
        }
        return true;
    }
}