LeetCode/solutions/cpp/0131.cpp at master · SnistAheads/LeetCode · GitHub

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
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        vector<string> path;
        dfs(s, 0, path, ans);
        return ans;
    }

private:
    void dfs(string& s, int j, vector<string>& path, vector<vector<string>>& ans) {
        if (j == s.length()) {
            ans.push_back(path);
            return;
        }

        for (int i = j; i < s.length(); i++)
            if (isPalindrome(s, j, i)) {
                path.push_back(s.substr(j, i - j + 1));
                dfs(s, i + 1, path, ans);
                path.pop_back();
            }
    }

    bool isPalindrome(string& s, int l, int r) {
        while (l < r)
            if (s[l++] != s[r--])
                return false;
        return true;
    }
};