题解 | #所有的回文子串II#

考察知识点：递归

题目分析：

可以使用深度优先搜索的方式，枚举每一个字符，以每个字符为起点，查找合法的子串。

在找到结果后应按题目要求按字典序排序并去除相同的子串。

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    bool isPalindrome(string &s, int start, int end) {
        int left = start, right = end;
        while (left < right) {
            if (s[left++] != s[right--]) 
                return false;
        }
        return true;
    }
    void dfs(string &s, int start, vector<string> &result) {
        if (start == s.size() - 1) return;
        for (int end = start + 1; end < s.size(); end++) {
            if (isPalindrome(s, start, end)) {
                result.push_back(s.substr(start, end - start + 1));
            }
        }
        dfs(s, start + 1, result);
    }
    vector<string> partitionII(string s) {
        // write code here
        vector<string> result;
        dfs(s, 0, result);
        sort(result.begin(), result.end());
        result.erase(unique(result.begin(), result.end()), result.end());
        return result;
    }
};