Palindrome Partitioning

Description

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

Return all possible palindrome partitioning of s.

Example
Given s = "aab", return
[
  ["aa","b"],
  ["a","a","b"]
]

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
    vector<vector<string>> partition(string s) {
        // write your code here
        vector<vector<string>> result;
        if (s.empty()) {
            return result;
        }
        vector<string> row;
        //sort(s.begin(), s.end());
        helper(s, result, row, 0);
        return result;
    }
private:
    void helper(string& s, vector<vector<string>>& result,
        vector<string>& path, int start
    ) {
        if (start == s.size()) {
            result.push_back(path);
            return;
        }
        int len = s.size();
        //----------------------------------------------------
        // version 1
        // for condition use normal expression
        // substr need "(start, i - start + 1)", 
        //      b/c index operation needs compensate 1
        // helper need "i+1" to make i can reach len
        for (int i = start; i < len; ++i) {
            string prev = s.substr(start, i - start + 1);
            // cannot cut in start with i
            if (!isPalin(prev)) {
                continue;
            }
            // can cut in start with i
            path.push_back(prev);
            helper(s, result, path, i + 1);
            path.erase(path.begin() + path.size() - 1);
        }
        //----------------------------------------------------
        // version 2
        start + 1 => make sure i can reach len
        the substr will be (start, i - start) directly
        for (int i = start + 1; i <= len; ++i) {
            string prev = s.substr(start, i - start);
            // cannot cut in start with i
            if (!isPalin(prev)) {
                continue;
            }
            // can cut in start with i
            path.push_back(prev);
            helper(s, result, path, i);
            path.erase(path.begin() + path.size() - 1);
        }
        //----------------------------------------------------
        return;
    }
    // check itis palindrome
    bool isPalin(string& s) {
        int len = s.size();
        int left = 0;
        int right = len -1;
        while (left < right) {
            if (s[left] != s[right]) {
                return false;   
            }
            left++;
            right--;
        }
        return true;;
    }
};

Similar problems

x

Tags

x