Leetcode Palindrome Partitioning problem solution

In this Leetcode Palindrome Partitioning problem solution, we have Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. A palindrome string is a string that reads the same backward as forward.

Problem solution in Python.

class Solution(object):
    def partition(self, s):
        if not s:
            return []
        memo = {}
        def partition(cur):
            if cur==len(s):
                return [[]]
            if cur in memo:
                return memo[cur]
            res = []
            for i in xrange(cur,len(s)):
                if s[cur:i+1]==s[cur:i+1][::-1]:
                    for tmp in partition(i+1):
                        res.append([s[cur:i+1]]+tmp)
            memo[cur] = res
            return res
        return partition(0)

Problem solution in Java.

class Solution {
    List<List<String>> result = new ArrayList<>();
    
    public List<List<String>> partition(String s) {
        helper(s, 0, new ArrayList<>());
        return result;
    }
    
    public void helper(String s, int index, List<String> combination){
        if (index == s.length()) {
            result.add(new ArrayList<>(combination));
            return;
        }

        for (int i = index; i < s.length(); i++) {

            if (isValid(s.substring(index, i + 1))) {
                combination.add(s.substring(index, i + 1));
                helper(s, i + 1, combination);
                combination.remove(combination.size() - 1);
            }

        }
    }
    
    public boolean isValid(String s){
        if(s.length() == 1){
            return true;
        }
        int left  = 0;
        int right = s.length() - 1;
        
        while(left < right){
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
}

Problem solution in C++.

public:
    vector<vector<string>> partition(string_view s) {
        const int n = size(s);
        auto is_poly = [](string_view str) {
            for (int i = 0; i < size(str) / 2; ++i) {
                if (str[i] != str[size(str) - i - 1]) {
                    return false;
                }
            }
            return true;
        };
        vector<vector<string>> res;
        function<void(int i)> backtrack;
        vector<string> current;
        backtrack = [&](int idx) {
            if (idx == n) {
                res.push_back(current);
                return;
            }
            string str;
            for (int i = idx; i < n; ++i) {
                str += s[i];
                if (is_poly(str)) {
                    current.push_back(str);
                    backtrack(i + 1);
                    current.pop_back();
                }
            }
        };
        backtrack(0);
        return res;
    }

coding problems