Lời giải của mình:
- Để tìm longest palindromic substring của s, ta có thể dựa vào ý tưởng tìm longest common substring của s và chuỗi đảo của chính nó (rs), vì khi đảo lại s thì longest palindromic substring không đổi
VD: s là
xxxabcdcba và chuỗi đảo rs
là abcdcbaxxx, khi cho vào thuật toán lc substr sẽ tìm được abcdcba.
- Tuy nhiên longest common substring chưa chắc đã là palindromic string
VD: s là
xxxabcdxxxdcba thì rs là
abcdxxxdcbaxxx, khi tìm lcsubstr của 2 chuỗi sẽ ra dcba hoặc abcd, sai so với yêu cầu.
Vì thế khi tìm được 1 chuỗi con chung dài nhất, sẽ check xem chuỗi có phải là palindromic string không.
Thuật toán:
1. Áp dụng lcsubstr, tìm 1 chuỗi con chung của 2 s và rs.
2. Khi được 1 chuỗi con chung:
2.1 Nếu độ dài chuỗi <= độ dài longest palindromic substring hiện tại, quay lại bước 1.
2.2 Check xem chuỗi có phải palindromic string không, nếu không quay lại bước 1.
2.3 Update độ dài lớn nhất và vị trí của chuỗi trong s hoặc rs.
3. Sử dụng vị trí và độ dài tìm được để trả về chuỗi kết quả.
Code hơi messy chút vì viết cho chạy luôn, tối ưu thì sẽ chạy nhanh hơn và đỡ tốn memory hơn.
C++:
class Solution {
public:
string longestPalindrome(string s) {
string rs = std::string(s);
std::reverse(rs.begin(),rs.end());
int n = s.size();
//if (n <= 1) return s;
int arr[n+2][n+2];
memset(arr, 0, sizeof arr);
int maxVal = 0, maxX = 0, maxY = 0;
for (int i = 1; i <= n+1; ++i) {
for (int j = 1; j <= n+1; ++j) {
if (i < n+1 && j < n+1 && s[i-1] == rs[j-1]) {
arr[i][j] = arr[i-1][j-1] + 1;
}
else {
if (arr[i-1][j-1] > maxVal) {
int size = arr[i-1][j-1];
bool check = true;
for (int pl = 0; pl <= size/2; ++pl) {
if (s[i-2-pl] != s[i-1-size+pl]) {
check = false;
break;
}
}
if (check) {
maxX = i-2;
maxY = j-2;
maxVal = arr[i-1][j-1];
}
}
}
}
}
string ans = s.substr(maxX - maxVal + 1,maxVal);
return ans;
}
};
