Tìm Chuỗi Đối Xứng Dài Nhất

Full Bộ Tài Liệu Lập Trình C/C++ – Khóa Học Lập Trình C/C++

Đề 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;
   }

};