# 5 - Longest Palindromic Substring

## 解法一 - 暴力法

1. 頭跟尾的字母相同：分別把頭跟尾都往內移，然後繼續確認目前這個是不是 palindromic substring
2. 頭跟尾的字母不同：那就把頭往後移 & 尾往前移，然後分別確認兩個新產生的字串是不是 palindromic substring

``````class Solution {
public:
string longestPalindrome(string s) {
return findLPSLength(s, 0, s.length()-1);
}

private:
string findLPSLength(string& s, int start, int end) {
string res = "";
if(start > end)
return res;

if(start == end) {
res = "";
res += s[start];
return res;
}

int c1 = 0;
if(s[start] == s[end]) {
int remainLength = (end-start+1) - 2;
if(remainLength == findLPSLength(s, start+1, end-1).length())
c1 = remainLength+2;
}

string s2 = findLPSLength(s, start+1, end);
string s3 = findLPSLength(s, start, end-1);
int c2 = s2.length();
int c3 = s3.length();

int maxVal = max(c1, max(c2, c3));
if(maxVal == c1 && maxVal > 0) res = s.substr(start, end-start+1);
else if(maxVal == c2  && maxVal > 0) res = s2;
else if(maxVal == c3  && maxVal > 0) res = s3;

return res;
}
};
``````

## 解法二 - DP

``````class Solution {
public:
string longestPalindrome(string s) {
string res = "";
if(s.empty()) return res;
res += s[0];
int maxLen = 1;

// Init
int n = s.length();
vector<vector<bool>> dp(n, vector<bool>(n, false));
for(int i=0; i<n; i++) {
dp[i][i] = true;
}

// Build dp table
for(int start = n-1; start>=0; start--) {
for(int end=start+1; end<n; end++) {
if(s[start] == s[end]) {
// If the length of current string == 2
// Or the remaining string is also palindrome
if(end-start == 1 || dp[start+1][end-1] == true) {
dp[start][end] = true;
if(end-start+1 > maxLen) {
maxLen = end-start+1;
res = s.substr(start, end-start+1);
}
}
}
}
}

return res;
}
};
``````