LeetCode 131. Palindrome Partitioning

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        function<void(int, vector<string>&)> dfs = [&](int pos, vector<string>& cur) {
            if (pos == s.size()) {
                ans.push_back(cur);
                return;
            }
            for (int i = pos; i < s.size(); ++i) {
                if (!isPalindrome(s, pos, i)) continue;
                cur.push_back(s.substr(pos, i - pos + 1));
                dfs(i + 1, cur);
                cur.pop_back();
            }
        };
        vector<string> cur;
        dfs(0, cur);
        return ans;
    }
private:
    bool isPalindrome(string s, int i, int j) {
        while (i < j)
            if (s[i++] != s[j--]) return false;
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;

        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        for (int right = 0; right < s.size(); ++right)
            for (int left = 0; left <= right; ++left)
                if (s[left] == s[right] && (right - left <= 2 || dp[left + 1][right - 1]))
                    dp[left][right] = true;

        function<void(int, vector<string>&)> dfs = [&](int pos, vector<string>& cur) {
            if (pos == s.size()) {
                ans.push_back(cur);
                return;
            }
            for (int i = pos; i < s.size(); ++i) {
                if (!dp[pos][i]) continue;
                cur.push_back(s.substr(pos, i - pos + 1));
                dfs(i + 1, cur);
                cur.pop_back();
            }
        };

        vector<string> cur;
        dfs(0, cur);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;

        vector<vector<int>> dp(s.size(), vector<int>(s.size()));
        function<int(int, int)> isPalindrome = [&](int left, int right) {
            if (dp[left][right]) // 0 unsearched, 1 is palindrome, -1 is not palindrome.
                return dp[left][right];
            if (left >= right)
                return dp[left][right] = 1;
            return dp[left][right] = (s[left] == s[right] ? isPalindrome(left + 1, right - 1) : -1);
        };

        function<void(int, vector<string>&)> dfs = [&](int pos, vector<string>& cur) {
            if (pos == s.size()) {
                ans.push_back(cur);
                return;
            }
            for (int i = pos; i < s.size(); ++i)
                if (isPalindrome(pos, i) == 1) {
                    cur.push_back(s.substr(pos, i - pos + 1));
                    dfs(i + 1, cur);
                    cur.pop_back();
                }
        };

        vector<string> cur;
        dfs(0, cur);
        return ans;
    }
};