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

知识点

枚举 回文串

思路

枚举子串的起止点，判断是否是回文串即可，把结果加入set去重。

枚举起止点时间复杂度为

判断回文串的时间复杂度为

总体时间复杂度为

AC code (C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    vector<string> partitionII(string s) {
        int n = s.size();
        set<string> res;
        for (int i = 0; i < n; i ++) {
            for (int j = i + 1; j < n; j ++) {
                if (check(s, i, j)) res.insert(s.substr(i, j - i + 1));
            }
        }
        return vector<string>(res.begin(), res.end());
    }
    bool check(string& s, int l, int r) {
        if (r - l < 1) return false;
        for (int i = l, j = r; i < j; i ++, j --) {
            if (s[i] != s[j]) return false;
        }
        return true;
    }
};