Đề Bài:Cho một chuỗi string S, tìm chuỗi đối xứng dài nhất trong String S
Ví Dụ 1:
Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.
Ví Dụ 2:
Input: s = "cbbd" Output: "bb"
Lời Giải:
// Step 1: Use for loop, to check at each position in the loop // Step 2: At each pos in the string, get a possible symetric string // Step 3: Use find max algorithm, to get the longest symetric string string sub_palindromic_1(string s, int pos) // aba { int i = 1; while ((pos >= i) && (pos + i) < s.length()) { if (s[pos + i] != s[pos - i]) { break; } i++; } return s.substr(pos - i + 1, 2 * i - 1); } string sub_palindromic_2(string s, int pos) // abba { int j = 0; while ((pos + j + 1 < s.length()) && (pos >= j)) { if ((s[pos - j] != s[pos + j + 1])) { break; } j++; } return s.substr(pos - j + 1, 2 * j); } string longestPalindrome(string s) { string s_Max = ""; if (s.length() <= 1) { s_Max = s; } else { for (int i = 0; i < s.length(); i++) { string s_i; if (i == 0) { if (s[i] == s[i + 1]) { s_i = sub_palindromic_2(s, i); } } else if ((s[i - 1] == s[i + 1]) && (s[i] == s[i + 1])) { string s1 = sub_palindromic_1(s, i); string s2 = sub_palindromic_2(s, i); if (s1.length() < s2.length()) { s_i = s1; } else { s_i = s2; } } else if (s[i-1] == s[i+1]) { s_i = sub_palindromic_1(s, i); } else if (s[i] == s[i+1]) { s_i = sub_palindromic_2(s, i); } else { s_i.push_back(s[i]); } if (s_i.length() > s_Max.length()) { s_Max = s_i; } } } return s_Max; }
Cách 2:
class Solution { public: Solution(); ~Solution(); string longestPalindrome(string s) { if (s.length() < 1) return ""; int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1); int len = std::max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substr(start, end + 1); } private: int expandAroundCenter(string s, int left, int right) { int L = left, R = right; while (L >= 0 && R < s.length() && s[L] == s[R]) { L--; R++; } return R - L - 1; } };
The post Tìm Chuỗi Đối Xứng Dài Nhất first appeared on Techacademy.
Nhận xét
Đăng nhận xét