Palindrome Partitioning with Backtracking

Approach

Since we’re looking for substrings, we have start and end points. We traverse the string with start at 0, advancing end to find palindromes. When we find one, we push start forward and repeat. We can search recursively, but how do we record found substring combinations so that when we start from different positions, the common prefixes stay preserved? This calls for backtracking. After our recursive search returns, we need to pop out the current palindrome we’ve searched before continuing.

DFS + Backtracking

vector<vector<string>> partition(string s) {
    vector<vector<string>> res;
    vector<string> path;
    if (s.size()==0) return res;
    dfs(s, 0, path, res);
    return res;
}

// DFS search
void dfs(string &s, int idx, vector<string>& path, vector<vector<string>> &res) {
    // One complete search of the entire string ends, record this search's substring set
    if (idx==s.size()) {
        res.push_back(path);
        return;
    }

    for(int i=idx;i<s.size();++i) {
        // Search for palindrome from current position
        if (isPalindrome(s, idx, i)) {
            // Save current found string
            path.push_back(s.substr(idx, i-idx+1));
            // Recursively advance search
            dfs(s, i+1, path, res);
            // Backtrack current found string, prepare for next substring search
            path.pop_back();
        }
    }
}

// Check palindrome
bool isPalindrome(string &s, int i, int j) {
    int hi=j;
    int lo=i;
    while(lo<hi) {
        if (s[lo++]!=s[hi--]) return false;
    }
    return true;
}

#backtracking #palindromes #strings #dfs

Next Greater Element II: Two Approaches Palindromic Substrings