Bài 6 Leetcode: Zigzag Conversion

Đề bài:

Chuỗi “PAYPALISHIRING” được viết theo mẫu zigzag trên một số hàng đã cho như sau:

(bạn có thể muốn hiển thị mẫu này bằng một phông chữ cố định để đọc dễ hơn)

P   A   H   N
A P L S I I G
Y   I   R

Sau đó, đọc từng dòng một: “PAHNAPLSIIGYIR”

Viết mã để thực hiện chuyển đổi chuỗi theo mẫu zigzag với số hàng đã cho:

string convert(string s, int numRows);

Ví dụ 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Ví dụ 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Giải thích:
P     I    N
A   L S  I G
Y A   H R
P     I

Ví dụ 3:

Input: s = "A", numRows = 1
Output: "A"

Ràng buộc:

• 1 <= độ dài chuỗi s <= 1000
• chuỗi s chỉ gồm chữ cái tiếng Anh (viết thường và viết hoa), ‘,’ và ‘.’ .
• 1 <= numRows <= 1000.

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

class Solution {
 public:
  string convert(string s, int numRows) {
    string ans;
    vector<vector<char>> rows(numRows);
    int k = 0;
    int direction = (numRows == 1) - 1;

    for (const char c : s) {
      rows[k].push_back(c);
      if (k == 0 || k == numRows - 1)
        direction *= -1;
      k += direction;
    }

    for (const vector<char>& row : rows)
      for (const char c : row)
        ans += c;

    return ans;
  }
};

Đoạn mã trên triển khai thuật toán để chuyển đổi chuỗi theo mẫu zigzag với số hàng đã cho. Dưới đây là giải thích chi tiết về cách thuật toán hoạt động:

1. Khởi tạo một chuỗi rỗng `ans` để lưu kết quả chuyển đổi.
2. Khởi tạo một vector 2D `rows` với kích thước `numRows`, mỗi hàng là một vector chứa các ký tự.
3. Khởi tạo biến `k` đại diện cho hàng hiện tại, và biến `direction` đại diện cho hướng di chuyển (-1 hoặc 1).
4. Sử dụng vòng lặp for-each để duyệt qua từng ký tự `c` trong chuỗi `s`.
5. Thêm ký tự `c` vào hàng `k` trong `rows`.
6. Kiểm tra nếu hàng `k` là hàng đầu tiên hoặc hàng cuối cùng (`k == 0` hoặc `k == numRows – 1`), thì đổi hướng `direction` bằng cách nhân với -1.
7. Cập nhật giá trị `k` bằng cách thêm `direction`.
8. Kết thúc vòng lặp, `rows` sẽ chứa chuỗi đã chuyển đổi theo mẫu zigzag.
9. Sử dụng hai vòng lặp for-each lồng nhau để duyệt qua từng ký tự `c` trong từng hàng `row` trong `rows`, và thêm `c` vào chuỗi `ans`.
10. Trả về chuỗi `ans` là kết quả cuối cùng của chuyển đổi.

Thuật toán này sử dụng một mảng 2D để lưu các ký tự theo mẫu zigzag. Bằng cách duyệt qua chuỗi gốc và thêm ký tự vào từng hàng tương ứng trong mảng `rows`, thuật toán tạo ra một mảng chứa chuỗi đã chuyển đổi. Sau đó, các ký tự trong mảng được ghép lại thành một chuỗi kết quả và được trả về. Thuật toán hoạt động trong độ phức tạp thời gian O(n), 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 convert(String s, int numRows) {
    StringBuilder sb = new StringBuilder();
    List<Character>[] rows = new List[numRows];
    int k = 0;
    int direction = numRows == 1 ? 0 : -1;

    for (int i = 0; i < numRows; ++i)
      rows[i] = new ArrayList<>();

    for (final char c : s.toCharArray()) {
      rows[k].add(c);
      if (k == 0 || k == numRows - 1)
        direction *= -1;
      k += direction;
    }

    for (List<Character> row : rows)
      for (final char c : row)
        sb.append(c);

    return sb.toString();
  }
}

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

class Solution:
  def convert(self, s: str, numRows: int) -> str:
    rows = [''] * numRows
    k = 0
    direction = (numRows == 1) - 1

    for c in s:
      rows[k] += c
      if k == 0 or k == numRows - 1:
        direction *= -1
      k += direction

    return ''.join(rows)