Bài 5 Leetcode: Longest Palindromic Substring

Đề bài:

Cho một chuỗi s, hãy trả về chuỗi con đối xứng dài nhất trong s.

Ví dụ 1:

Input: s = "babad"
Output: "bab"
Giải thích: "aba" cũng là một câu trả lời hợp lệ.

Ví dụ 2:

Input: s = "cbbd"
Output: "bb"

Ràng buộc:

  • 1 <= độ dài của chuỗi s <= 1000
  • chuỗi s chỉ gồm chữ số và chữ cái tiếng Anh.

Cách 1: Naive

Giải thích thuật toán bằng C+

class Solution {
 public:
  string longestPalindrome(string s) {
    if (s.empty())
      return "";

    // [start, end] indices of the longest palindrome in s
    pair<int, int> indices{0, 0};

    for (int i = 0; i < s.length(); ++i) {
      const auto [l1, r1] = extend(s, i, i);
      if (r1 - l1 > indices.second - indices.first)
        indices = {l1, r1};
      if (i + 1 < s.length() && s[i] == s[i + 1]) {
        const auto [l2, r2] = extend(s, i, i + 1);
        if (r2 - l2 > indices.second - indices.first)
          indices = {l2, r2};
      }
    }

    return s.substr(indices.first, indices.second - indices.first + 1);
  }

 private:
  // Returns [start, end] indices of the longest palindrome extended from
  // s[i..j]
  pair<int, int> extend(const string& s, int i, int j) {
    for (; i >= 0 && j < s.length(); --i, ++j)
      if (s[i] != s[j])
        break;
    return {i + 1, j - 1};
  }
};

Đoạn mã trên triển khai thuật toán để tìm chuỗi con đối xứng dài nhất trong chuỗi s. Dưới đây là giải thích chi tiết về cách thuật toán hoạt động:

1. Kiểm tra xem chuỗi s có rỗng không. Nếu có, trả về chuỗi rỗng.
2. Khởi tạo một cặp chỉ số indices để lưu vị trí bắt đầu và kết thúc của chuỗi con đối xứng dài nhất trong s. Ban đầu, indices = {0, 0}.
3. Bắt đầu một vòng lặp từ i = 0 đến i < độ dài của chuỗi s.
4. Trong mỗi vòng lặp, mở rộng chuỗi con đối xứng từ vị trí i bằng cách sử dụng hàm extend(s, i, i). Hàm extend này sẽ trả về cặp chỉ số [l1, r1] của chuỗi con đối xứng dài nhất được mở rộng từ vị trí i trong cả hai hướng.
5. Kiểm tra nếu độ dài của chuỗi mới mở rộng (r1 – l1) lớn hơn độ dài của chuỗi đã lưu trong indices (indices.second – indices.first), thì cập nhật indices = {l1, r1}.
6. Kiểm tra nếu i + 1 < độ dài của chuỗi s và s[i] == s[i + 1]. Nếu điều kiện này được thỏa mãn, mở rộng chuỗi con đối xứng từ vị trí i và i + 1 bằng cách sử dụng hàm extend(s, i, i + 1). Hàm extend này trả về cặp chỉ số [l2, r2] của chuỗi con đối xứng dài nhất được mở rộng từ vị trí i và i + 1.
7. Kiểm tra nếu độ dài của chuỗi mới mở rộng (r2 – l2) lớn hơn độ dài của chuỗi đã lưu trong indices, thì cập nhật indices = {l2, r2}.
8. Kết thúc vòng lặp, trả về chuỗi con đối xứng tương ứng trong chuỗi s bằng cách sử dụng hàm substr(indices.first, indices.second – indices.first + 1).
9. Trong phần riêng tư của lớp, có hàm extend(s, i, j) được triển khai để mở rộng chuỗi con đối xứng từ vị trí i và j trong chuỗi s. Hàm này sử dụng kỹ thuật hai con trỏ để mở rộng chuỗi con đối xứng từ vị trí i và j trong cả hai hướng, và trả về cặp chỉ số [start, end] của chuỗi con đối xứng dài nhất đã mở rộng.

Thuật toán này sử dụng kỹ thuật trượt cửa sổ và hai con trỏ để tìm chuỗi con đối xứng dài nhất trong chuỗi s. Bằng cách tìm kiếm và mở rộng từng chuỗi con tại mỗi vị trí, thuật toán đảm bảo tìm được chuỗi con đối xứng dài nhất trong độ phức tạp thời gian O(n^2), trong đó n là độ dài của chuỗi s.

Giải thích thuật toán bằng Java

class Solution {
  public String longestPalindrome(String s) {
    if (s.isEmpty())
      return "";

    // (start, end) indices of the longest palindrome in s
    int[] indices = {0, 0};

    for (int i = 0; i < s.length(); ++i) {
      int[] indices1 = extend(s, i, i);
      if (indices1[1] - indices1[0] > indices[1] - indices[0])
        indices = indices1;
      if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
        int[] indices2 = extend(s, i, i + 1);
        if (indices2[1] - indices2[0] > indices[1] - indices[0])
          indices = indices2;
      }
    }

    return s.substring(indices[0], indices[1] + 1);
  }

  // Returns the (start, end) indices of the longest palindrome extended from
  // the substring s[i..j].
  private int[] extend(final String s, int i, int j) {
    for (; i >= 0 && j < s.length(); --i, ++j)
      if (s.charAt(i) != s.charAt(j))
        break;
    return new int[] {i + 1, j - 1};
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def longestPalindrome(self, s: str) -> str:
    if not s:
      return ''

    # (start, end) indices of the longest palindrome in s
    indices = [0, 0]

    def extend(s: str, i: int, j: int) -> Tuple[int, int]:
      """
      Returns the (start, end) indices of the longest palindrome extended from
      the substring s[i..j].
      """
      while i >= 0 and j < len(s):
        if s[i] != s[j]:
          break
        i -= 1
        j += 1
      return i + 1, j - 1

    for i in range(len(s)):
      l1, r1 = extend(s, i, i)
      if r1 - l1 > indices[1] - indices[0]:
        indices = l1, r1
      if i + 1 < len(s) and s[i] == s[i + 1]:
        l2, r2 = extend(s, i, i + 1)
        if r2 - l2 > indices[1] - indices[0]:
          indices = l2, r2

    return s[indices[0]:indices[1] + 1]

Cách 2: Manacher

Giải thích thuật toán bằng C ++

class Solution {
 public:
  string longestPalindrome(string s) {
    // '@' and '$' signs serve as sentinels appended to each end to avoid bounds
    // checking.
    const string& t = join('@' + s + '$', '#');
    const int n = t.length();
    // t[i - maxExtends[i]..i) ==
    // t[i + 1..i + maxExtends[i]]
    vector<int> maxExtends(n);
    int center = 0;

    for (int i = 1; i < n - 1; ++i) {
      const int rightBoundary = center + maxExtends[center];
      const int mirrorIndex = center - (i - center);
      maxExtends[i] =
          rightBoundary > i && min(rightBoundary - i, maxExtends[mirrorIndex]);

      // Attempt to expand the palindrome centered at i.
      while (t[i + 1 + maxExtends[i]] == t[i - 1 - maxExtends[i]])
        ++maxExtends[i];

      // If a palindrome centered at i expand past `rightBoundary`, adjust
      // center based on expanded palindrome.
      if (i + maxExtends[i] > rightBoundary)
        center = i;
    }

    // Find the `maxExtend` and `bestCenter`.
    int maxExtend = 0;
    int bestCenter = -1;

    for (int i = 0; i < n; ++i)
      if (maxExtends[i] > maxExtend) {
        maxExtend = maxExtends[i];
        bestCenter = i;
      }

    const int l = (bestCenter - maxExtend) / 2;
    const int r = (bestCenter + maxExtend) / 2;
    return s.substr(l, r - l);
  }

 private:
  string join(const string& s, char c) {
    string joined;
    for (int i = 0; i < s.length(); ++i) {
      joined += s[i];
      if (i != s.length() - 1)
        joined += c;
    }
    return joined;
  }
};

Đoạn mã trên là một phương thức trong lớp `Solution` được viết bằng ngôn ngữ C++ để tìm chuỗi con đối xứng dài nhất trong một chuỗi đầu vào.

Phương thức `longestPalindrome` nhận đầu vào là một chuỗi `s` và trả về một chuỗi con đối xứng dài nhất trong `s`.

Ban đầu, một chuỗi `t` được tạo ra bằng cách thêm các ký tự đặc biệt ‘@’ và ‘$’ vào hai đầu của chuỗi `s`, cùng với ký tự đặc biệt ‘#’ được chèn giữa các ký tự của `s`. Điều này được thực hiện để đảm bảo rằng không cần kiểm tra ràng buộc chỉ số khi truy cập vào `t`.

Một vector `maxExtends` được khởi tạo với kích thước n (chiều dài của chuỗi `t`) và các phần tử ban đầu là 0. Vector này được sử dụng để lưu trữ độ dài của chuỗi con đối xứng tại mỗi vị trí `i` trong `t`.

Biến `center` được khởi tạo với giá trị 0, đại diện cho chỉ số của trung tâm hiện tại của chuỗi con đối xứng.

Vòng lặp for đầu tiên được sử dụng để duyệt qua các vị trí từ 1 đến n-1 trong chuỗi `t`.

Trong mỗi vòng lặp, biến `rightBoundary` được tính bằng cách cộng giá trị của `center` với `maxExtends[center]`, đại diện cho ranh giới bên phải của chuỗi con đối xứng.

Biến `mirrorIndex` được tính bằng cách lấy giá trị của `center` trừ đi hiệu của `i` và `center`, đại diện cho chỉ số tương ứng với đối xứng của `i` qua trung tâm.

`maxExtends[i]` được tính bằng giá trị nhỏ nhất giữa `rightBoundary – i` và `maxExtends[mirrorIndex]`. Điều này đảm bảo rằng `maxExtends[i]` sẽ lưu trữ độ dài của chuỗi con đối xứng tại vị trí `i`.

Tiếp theo, một vòng lặp while được sử dụng để mở rộng chuỗi con đối xứng tại vị trí `i`. Vòng lặp này sẽ tiếp tục cho đến khi ký tự tại vị trí `i + 1 + maxExtends[i]` và `i – 1 – maxExtends[i]` trong `t` khác nhau.

Nếu chuỗi con đối xứng mở rộng tại vị trí `i` vượt qua giới hạn `rightBoundary`, trung tâm `center` được điều chỉnh dựa trên chuỗi con đối xứng đã mở rộng.

Sau khi vòng lặp kết thúc, `maxExtend` và `bestCenter` được tìm ra. `maxExtend` lưu trữ độ dài của chuỗi con đối xứng dài nhất và `bestCenter` lưu trữ chỉ số của trung tâm của chuỗi con đối xứng.

Cuối cùng, chỉ số bắt đầu `l` và chỉ số kết thúc `r` của chuỗi con đối xứng dài nhất được tính dựa trên `bestCenter` và `maxExtend`. Chuỗi con đối xứng này được trích xuất từ chuỗi `s` bằng cách sử dụng hàm `substr` và được trả về.

Giải thích thuật toán bằng Java

class Solution {
  public String longestPalindrome(String s) {
    // '@' and '$' signs serve as sentinels appended to each end to avoid bounds
    // checking.
    final String t = join('@' + s + '$', '#');
    final int n = t.length();
    // t[i - maxExtends[i]..i) ==
    // t[i + 1..i + maxExtends[i]]
    int[] maxExtends = new int[n];
    int center = 0;

    for (int i = 1; i < n - 1; ++i) {
      final int rightBoundary = center + maxExtends[center];
      final int mirrorIndex = center - (i - center);
      maxExtends[i] =
          rightBoundary > i && Math.min(rightBoundary - i, maxExtends[mirrorIndex]) > 0 ? 1 : 0;

      // Attempt to expand the palindrome centered at i.
      while (t.charAt(i + 1 + maxExtends[i]) == t.charAt(i - 1 - maxExtends[i]))
        ++maxExtends[i];

      // If a palindrome centered at i expand past `rightBoundary`, adjust
      // center based on expanded palindrome.
      if (i + maxExtends[i] > rightBoundary)
        center = i;
    }

    // Find the `maxExtend` and `bestCenter`.
    int maxExtend = 0;
    int bestCenter = -1;

    for (int i = 0; i < n; ++i)
      if (maxExtends[i] > maxExtend) {
        maxExtend = maxExtends[i];
        bestCenter = i;
      }

    return s.substring((bestCenter - maxExtend) / 2, (bestCenter + maxExtend) / 2);
  }

  private String join(final String s, char c) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); ++i) {
      sb.append(s.charAt(i));
      if (i != s.length() - 1)
        sb.append(c);
    }
    return sb.toString();
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def longestPalindrome(self, s: str) -> str:
    # '@' and '$' signs serve as sentinels appended to each end to avoid bounds
    # checking.
    t = '#'.join('@' + s + '$')
    n = len(t)
    # t[i - maxExtends[i]..i) ==
    # t[i + 1..i + maxExtends[i]]
    maxExtends = [0] * n
    center = 0

    for i in range(1, n - 1):
      rightBoundary = center + maxExtends[center]
      mirrorIndex = center - (i - center)
      maxExtends[i] = rightBoundary > i and \
          min(rightBoundary - i, maxExtends[mirrorIndex])

      # Attempt to expand the palindrome centered at i.
      while t[i + 1 + maxExtends[i]] == t[i - 1 - maxExtends[i]]:
        maxExtends[i] += 1

      # If a palindrome centered at i expand past `rightBoundary`, adjust
      # center based on expanded palindrome.
      if i + maxExtends[i] > rightBoundary:
        center = i

    # Find the `maxExtend` and `bestCenter`.
    maxExtend, bestCenter = max((extend, i)
                                for i, extend in enumerate(maxExtends))
    return s[(bestCenter - maxExtend) // 2:(bestCenter + maxExtend) // 2]

 

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.