LeetCode: Palindrome Partitioning

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

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

---

Use DFS to check every possible partition.

C++ Code:

/*
 * func: valid_palindrome
 * goal: to validate the input string
 * @param s: input string
 * @param left: left searching index
 * @param right: right searching index
 * return:
 */
bool valid_palindrome(string s, int left, int right){
    while(left <= right){
        if(s[left] != s[right]){
            return false;
        }else{
            ++left;
            --right;
        }
    }
    return true;
}

/*
 * func: generate_combination
 * goal: use DFS to generate combinations
 * @param s: input string
 * @param start: start searching index
 * @param combination: current combination
 * @param result: final result set
 * return:
 */
void generate_combination(string s, int start, vector<string> &combination, vector<vector<string> > &result){
    if(start >= s.length()){
        result.emplace_back(combination);
        return;
    }
    for(int i = start; i < s.length(); ++i){
        if(valid_palindrome(s, start, i)){
            string tmp = s.substr(start, i-start+1);
            combination.emplace_back(tmp);
            generate_combination(s, i+1, combination, result);
            combination.pop_back();
        }
    }
}


/*
 * func: palindrome_partition
 * goal: return all possible palindrome partitioning of input string
 * @param s: input string
 * return: all possible combinations
 */
vector<vector<string> > palindrome_partition(string s){
    vector<vector<string> > result;
    vector<string> combination;
    generate_combination(s, 0, combination, result);
    return result;
}

Python Code:

# func: valid if current string is a palindrome
# @param start: start searching index
# @param end: end searching index
# @return: True or False
def valid_palindrome(s, start, end):
    while start <= end:
        if s[start] != s[end]:
            return False
        else:
            start += 1
            end -= 1
    return True

# func: find all possible palindrome partitioning of input string
# @param s: input string
# @return: all possible partitions
def palindrome_partition(s):
    result = []
    combination = []
    def palindrome_partition_helper(start):
        if start >= len(s):
            result.append(combination[:])
            return

        for i in xrange(start, len(s)):
            if valid_palindrome(s, start, i):
                combination.append(s[start:i+1])
                palindrome_partition_helper(i+1)
                combination.pop(-1)
    palindrome_partition_helper(0)
    return result