Chương trình tìm chỉ số bắt đầu của tất cả anagram của chuỗi S trong T với Python

Mô tả bài toán

Cho hai chuỗi S và T, tìm tất cả chỉ số bắt đầu của các anagram của S trong T. Chuỗi chỉ chứa chữ cái thường, độ dài S ≤ 20, T ≤ 100.

Ví dụ: S = "cab", T = "bcabxabc" → Kết quả: [0, 1, 5] (các xâu con: "bca", "cab", "abc").

Thuật toán

1. Tạo bản đồ tần suất ký tự của S.
2. Duyệt qua T với cửa sổ trượt, cập nhật bộ đếm.
3. Khi bộ đếm về 0, thêm chỉ số bắt đầu vào kết quả.
4. Xử lý trường hợp ký tự không khớp bằng cách dịch chuyển cửa sổ.

Triển khai Python

class Solution:
    def findAnagrams(self, s: str, p: str) -> list[int]:
        from collections import Counter
        
        m = Counter(p)
        n = len(s)
        left = 0
        counter = len(p)
        ans = []
        
        for right in range(n):
            if m.get(s[right], 0) > 0:
                m[s[right]] -= 1
                counter -= 1
                if counter == 0:
                    ans.append(left)
            else:
                while left < right:
                    if s[left] in m:
                        m[s[left]] += 1
                        counter += 1
                    left += 1
                    if m.get(s[right], 0) > 0:
                        right -= 1
                        break
                if s[left] not in m:
                    left = right + 1
        
        return ans

# Test
ob = Solution()
print(ob.findAnagrams("bcabxabc", "cab"))

Đầu vào: "bcabxabc", "cab"

Đầu ra: [0, 1, 5]

Giải thích

• Sử dụng Counter để đếm tần suất ký tự của chuỗi mẫu p.
• Duyệt chuỗi s với con trỏ right, mở rộng cửa sổ.
• Khi gặp ký tự có trong mẫu, giảm bộ đếm. Khi counter == 0 tìm thấy anagram.
• Khi gặp ký tự không trong mẫu, thu hẹp cửa sổ từ trái (left) cho đến khi cửa sổ hợp lệ lại.