Chương trình tìm tất cả chuỗi con có anagram xuất hiện trong chuỗi trong Python

Cho chuỗi s chữ thường. Tìm tất cả chuỗi con của s mà tồn tại một chuỗi con khác tại vị trí khác là anagram của nó. Trả về danh sách theo thứ tự từ điển.

Ví dụ: s = "abcba" → kết quả ['a','a','ab','abc','abcb','b','b','ba','bc','bcba','cb','cba'].

Thuật toán giải quyết

1. Với mỗi độ dài i từ 1 đến len(s):
   • Duyệt mọi chuỗi con độ dài i
   • Tính "fingerprint" = chuỗi ký tự đã sắp xếp
   • Gom nhóm chuỗi con theo fingerprint trong defaultdict(list)
2. Nếu một nhóm có ≥ 2 chuỗi con: thêm tất cả vào kết quả
3. Sắp xếp kết quả và trả về

Ví dụ minh họa

from collections import defaultdict

def solve(s):
    res = []
    L = len(s)
    for i in range(1, L + 1):
        smap = defaultdict(list)
        for j in range(L - i + 1):
            cs = s[j:j+i]
            k = "".join(sorted(cs))
            smap[k].append(cs)
        for k, v in smap.items():
            if len(v) >= 2:
                res.extend(v)
    return sorted(res)

s = "abcba"
print(solve(s))

Đầu vào

"abcba"

Đầu ra

['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba', 'bc', 'bcba', 'cb', 'cba']