Kiểm tra biến đổi chuỗi A thành B với ràng buộc di chuyển A/B (Python)

Bài toán: Hai chuỗi s, t chỉ chứa 'A', 'B', '#'. Cho phép: 'A' chỉ dịch trái, 'B' chỉ dịch phải, 'A' và 'B' không được vượt qua nhau. Kiểm tra s → t.

Quan sát

• Thứ tự tương đối của 'A' và 'B' không đổi (không vượt qua nhau).
• 'A' chỉ có thể di chuyển sang trái (index giảm).
• 'B' chỉ có thể di chuyển sang phải (index tăng).
• '#' là khoảng trống.

Triển khai Python

def solve(s, t):
    s, t = list(s), list(t)
    if len(s) != len(t):
        return False
    if s.count('A') != t.count('A') or s.count('B') != t.count('B'):
        return False
    
    for i in range(len(s)):
        if s[i] != '#':
            for j in range(len(t)):
                if t[j] != '#' and t[j] != s[i]:
                    return False
                if t[j] == s[i]:
                    t[j] = '#'  # Đánh dấu đã match
                    if s[i] == 'A' and i < j:
                        return False  # A chỉ đi trái (index giảm)
                    if s[i] == 'B' and i > j:
                        return False  # B chỉ đi phải (index tăng)
                    break
    return True

# Test
print(solve("##AB##B", "A###B#B"))  # True
# s: ## A B ## B  (indices: A=2, B=3, B=6)
# t: A ### B # B (indices: A=0, B=4, B=6)
# A: 2→0 (trái OK), B: 3→4 (phải OK), B: 6→6 (OK)
print(solve("A#B", "BA#"))          # False: A,B order changed

Kết quả

True

Giải thích

• Kiểm tra độ dài và số lượng 'A'/'B' khớp nhau.
• Duyệt s, với mỗi 'A'/'B' tìm ký tự tương ứng đầu tiên trong t (bỏ qua '#').
• Kiểm tra ràng buộc di chuyển: 'A' chỉ từ index lớn → nhỏ, 'B' từ nhỏ → lớn.
• Đánh dấu t[j] = '#' sau khi match để không dùng lại.
• Độ phức tạp: O(n²) worst-case, có thể tối ưu O(n) bằng two pointers.