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

考察的知识点：回文；

解答方法分析：

1. 定义一个空的vector result来存储结果，及一个unordered_set seen来存储已经遍历过的回文子串，以去重。
2. 通过一个循环遍历字符串s的每个字符，以字符i为中心，分别判断以i为中心和以(i, i+1)为中心的回文子串。
3. 在expandPalindrome函数中，使用双指针，从中心向两边扩展判断回文串。当left和right指向的字符相同时，将回文串s.substr(left, right-left+1)加入到result中。
4. 注意，需要判断回文串长度是否超过1，并且确保没有重复的回文子串。
5. 在一次判断完毕后将left和right向两边移动，以继续判断下一组回文串。
6. 对result中的回文子串进行排序，以便按字典序返回结果。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    vector<string> partitionII(string s) {
        vector<string> result;
        unordered_set<string> seen;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            expandPalindrome(s, i, i, result, seen);
            expandPalindrome(s, i, i + 1, result, seen);
        }

        sort(result.begin(), result.end());

        return result;
    }

  private:
    void expandPalindrome(string& s, int left, int right, vector<string>& result,
                          unordered_set<string>& seen) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            string palindrome = s.substr(left, right - left + 1);
            if (right - left + 1 > 1 && seen.find(palindrome) == seen.end()) {
                seen.insert(palindrome);
                result.push_back(palindrome);
            }
            left--;
            right++;
        }
    }
};