코테준비 - Longest Palindromic Substring

Longest Palindromic Substring

class Solution {
private:
    unordered_map<string, bool> palindromeMap;
    unordered_map<string, set<vector<string>>> DP;
public:
    vector<vector<string>> partition(string s) {
        auto res = recursive(s);

        return vector<vector<string >>(res.begin(), res.end());
    }

    set<vector<string>> recursive(string s) {
        if (DP.find(s) != DP.end()) {
            return DP[s];
        }

        if (s.length() == 1) {
            DP[s] = {{s}};
            return {{s}};
        }

        set<vector<string>> tempTemp;
        for (int i =  1; i < s.length(); i++) {
            auto left = recursive(s.substr(0, i));
            auto right = recursive(s.substr(i, s.length() - i + 1));

            if(s == "tdd") {
                int a = 9;
            }

            for (auto &l: left) {
                for (auto &r: right) {
                    vector<string> temp(l);
                    temp.insert(temp.end(), r.begin(), r.end());
                    tempTemp.insert(temp);
                }
            }
            // is s pelindrome?
            if (isPalindrome(s)) {
                tempTemp.insert({s});
            }

        }

        DP[s] = tempTemp;
        return tempTemp;
    }

    bool isPalindrome(string s){
        int strLen = s.length();

        if (s.length() & 1) {
            for (int cen = 0; cen < strLen; cen++) {
                for (int wid = 0; cen - wid >= 0 && cen + wid < strLen; wid++) {
                    if (!recursiveCheck(s, cen - wid, cen + wid)) {
                        return false;
                    }
                }
            }
        } else {
            for (int cen = 0; cen < strLen; cen++) {
                for (int wid = 0; cen - wid >= 0 && cen + 1 + wid < strLen; wid++) {
                    if (!recursiveCheck(s, cen - wid, cen + 1 + wid)) {
                        return false;
                    }
                }
            }
        }
        
        return true;
    }

    bool recursiveCheck(std::string &s, int i, int k) {
        if (i >= k)
            return true;
        auto subStr = s.substr(i, k - i + 1);
        if (palindromeMap.find(subStr) != palindromeMap.end())
            return palindromeMap[subStr];
        else if (s.at(i) == s.at(k)) {
            bool isSubStrPalindrome = recursiveCheck(s, i + 1, k - 1);
            if (isSubStrPalindrome) return true;
        }
        return false;
    }
};