Thuật toán Zigzag Conversion

🔗 Link bài toán: Zigzag Conversion - LeetCode

1. Mô tả yêu cầu

Chuỗi "PAYPALISHIRING" được viết theo dạng zigzag trên số lượng n dòng được cho sẵn.

Ví dụ với numRows = 3:

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

Sau đó, chuỗi kết quả được đọc theo từng dòng: "PAHNAPLSIIGYIR".

Ví dụ

2. Phân tích thuật toán

Bài toán yêu cầu đầu vào là một chuỗi s và một số nguyên numRows, trả về chuỗi được sắp xếp theo quy tắc zigzag.

• Nếu numRows = 1, thuật toán sẽ trả về chính s mà không cần xử lý gì thêm.
• Với numRows > 1, chúng ta cần tìm cách viết lại chuỗi theo mẫu zigzag.

3. Lời giải

Phương pháp 1: Dùng mảng 2D để lưu các hàng

Ý tưởng

• Sử dụng một vector 2D (vec_n) để lưu các ký tự theo thứ tự zigzag.
• Duyệt từng ký tự trong chuỗi đầu vào, thêm vào hàng hiện tại, sau đó điều chỉnh hướng đi lên hoặc xuống dựa trên vị trí hiện tại.
• Cuối cùng, nối tất cả các hàng để tạo thành chuỗi kết quả.

Cài đặt

pub fn sol1(s: String, num_rows: i32) -> String {
    let mut vec_n: Vec<Vec<char>> = vec![vec![]; num_rows as usize];
    let mut i: i32 = 0;
    let mut j: i32 = 1;
    if num_rows <= 1 {
        return s;
    }

    for c in s.chars() {
        vec_n[i as usize].push(c);
        i += j;
        if i == 0 || i == num_rows - 1 {
            j = -j;
        }
    }

    let mut result = String::new();
    for v in vec_n {
        for c in v {
            result.push(c);
        }
    }
    result
}

Phân tích độ phức tạp

• Thời gian: (O(n)) - Mỗi ký tự được duyệt đúng một lần.
• Không gian: (O(n)) - Chúng ta lưu tất cả các ký tự vào một mảng 2D trước khi kết hợp lại.

Phương pháp 2: Tính toán vị trí trực tiếp

Ý tưởng

• Thay vì lưu các ký tự vào mảng 2D, chúng ta trực tiếp tính toán vị trí của từng ký tự trong kết quả đầu ra.
• Nhận thấy rằng với dòng đầu tiên và dòng cuối cùng, các ký tự cách nhau một khoảng 2(numRows - 1).
• Với các dòng ở giữa, ta cần xen kẽ giữa hai bước nhảy:
  • 2(numRows - i - 1)
  • 2(i)

Cài đặt

pub fn sol2(s: String, num_rows: i32) -> String {
    let mut result = String::new();
    if num_rows == 1 {
        return s;
    }
    for i in 0..num_rows {
        let mut j = i;
        let mut flag = true;
        while j < s.len() as i32 {
            result.push(s.chars().nth(j as usize).unwrap());
            if i == 0 || i == num_rows - 1 {
                j += 2 * num_rows - 2;
            } else {
                if flag {
                    j += 2 * (num_rows - i - 1);
                    flag = false;
                } else {
                    j += 2 * i;
                    flag = true;
                }
            }
        }
    }
    result
}

Phân tích độ phức tạp

• Thời gian: (O(n)) - Chúng ta duyệt qua mỗi ký tự trong chuỗi một lần.
• Không gian: (O(n)) - Chúng ta chỉ lưu chuỗi kết quả, không sử dụng mảng 2D phụ trợ.

4. So sánh hai phương pháp

5. Kết luận

• Phương pháp 1 (Vector 2D) dễ hiểu hơn nhưng tốn bộ nhớ do lưu toàn bộ chuỗi vào mảng 2D trước khi kết hợp lại.
• Phương pháp 2 (Tính toán vị trí trực tiếp) tối ưu hơn về không gian nhưng khó triển khai hơn.
• Cả hai phương pháp đều có độ phức tạp thời gian là (O(n)), nhưng phương pháp 2 tiết kiệm bộ nhớ hơn.
• Khi numRows nhỏ, phương pháp 1 có thể phù hợp hơn. Khi numRows lớn, phương pháp 2 sẽ hoạt động hiệu quả hơn.