In Từ Theo Chiều Dọc (Print Vertically) Trong Python: LeetCode Style

Đề bài: Cho chuỗi s gồm các từ cách nhau bởi dấu cách. Trả về list các chuỗi đại diện cho việc đọc theo cột (dọc), từ trái sang phải, trên xuống dưới. Padding bằng space nếu cần, không giữ trailing space.

Ví dụ: "HOW ARE YOU" → ["HAY", "ORO", "WEU"]

H A Y
O R O
W E U

Thuật toán

1. Tách chuỗi thành list từ: words = s.split().
2. Tìm độ dài từ dài nhất → số hàng rows.
3. Số cột cols = len(words).
4. Khởi tạo mảng kết quả ans = [""] * rows.
5. Duyệt từng cột i, từng hàng j:
   • Nếu từ words[i] có ký tự thứ j → thêm vào ans[j].
   • Ngược lại → thêm space (padding).
6. Loại bỏ trailing space của mỗi hàng (rstrip).

Code Python

class Solution:
    def printVertically(self, s: str) -> list[str]:
        words = s.split()
        rows = max(len(w) for w in words)
        cols = len(words)
        ans = [""] * rows
        
        for i in range(cols):
            word = words[i]
            for j in range(rows):
                if j < len(word):
                    ans[j] += word[j]
                else:
                    ans[j] += " "
        
        # Xóa trailing space
        return [row.rstrip() for row in ans]

# Test
ob = Solution()
print(ob.printVertically("HOW ARE YOU"))        # ['HAY', 'ORO', 'WEU']
print(ob.printVertically("TO BE OR NOT TO BE")) # ['TBONTB', 'OEROOE', '   T']

Kết quả

['HAY', 'ORO', 'WEU']
['TBONTB', 'OEROOE', '   T']

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

• Time: O(N * M) với N = số từ, M = độ dài từ max.
• Space: O(N * M) cho output.

Kết luận

Bài toán mô phỏng ma trận chữ, cần xử lý cẩn thận padding và rstrip. Cách làm trực quan, dễ hiểu, phù hợp interview.