[C++] Palindrome

Palindrome

1. 개념

Palindrome은 거꾸로 읽어도 제대로 읽는 것과 같은 문장을 말한다.

 

Palindrome

 

2. 문제

https://leetcode.com/problems/palindrome-partitioning/description/

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<vector<string>> answer;
    vector<string> sub;

    vector<vector<string>> partition(string s) {
        dfs(s, 0);
        return answer;
    }

    void dfs(string s, int index) {
        if (index == s.length()) {
            answer.push_back(sub);
            return;
        }

        for (int i = index; i < s.length(); i++) {
            string substr = s.substr(index, i - index + 1);
            if (!palindrome(substr))
                continue;
            sub.push_back(substr);
            dfs(s, i + 1);
            sub.pop_back();
        }
    }

    bool palindrome(string s) {
        int size = s.length();
        for (int i = 0; i < size / 2; i++)
            if (s[i] != s[size - i - 1])
                return false;
        return true;
    }
};

 

https://leetcode.com/problems/longest-palindromic-substring/description/

#include <string>
using namespace std;

class Solution {
public:
	bool dp[1001][1001]{};

	string longestPalindrome(string s) {
		// 1글자
		string answer = s.substr(0, 1);
		for (int i = 0; i < s.size(); i++)
			dp[i][i] = true;

		// 2글자
		for (int i = 0; i < s.size() - 1; i++)
			if (s[i] == s[i + 1]) {
				dp[i][i + 1] = true;
				answer = s.substr(i, 2);
			}

		// 3글자 이상
		for (int i = 3; i <= s.size(); i++)
			for (int j = 0; j + i <= s.size(); j++)
				if (dp[j + 1][j + i - 2] && s[j] == s[j + i - 1]) {
					dp[j][j + i - 1] = true;
					if (answer.size() < i)
						answer = s.substr(j, i);
				}

		return answer;
	}
};

 

https://leetcode.com/problems/shortest-palindrome/description/

#include <string>
using namespace std;

class Solution {
public:
    string shortestPalindrome(string s) 
    {
        int i = 0, n = s.size();
        for (int j = n - 1; j >= 0; --j)
            if (s[i] == s[j]) 
                ++i;

        if (i == n) 
            return s;

        string add = s.substr(i); // 추가해야 할 최소 문자열
        reverse(add.begin(), add.end());
        return add + shortestPalindrome(s.substr(0, i)) + s.substr(i);
    }
};