โปรแกรมหา Substring ทั้งหมดที่มี Anagram อยู่ในสตริงเดียวกันใน Python

ให้สตริง s หา Substring ทุกตัวที่มี Anagram อีกตัวหนึ่งอยู่ใน s ตำแหน่งต่างกัน เรียงผลลัพธ์เล็กซิโคกราฟิก

ตัวอย่าง: s="abcba" → ['a','a','ab','abc','abcb','b','b','ba','bc','bcba','cb','cba']

ขั้นตอน

1. วนความยาว Substring i = 1..L
2. สร้าง Map smap Key = Sorted Substring, Value = ลิสต์ Substring ต้นฉบับ
3. ถ้า Key มี ≥ 2 ค่า → เพิ่มทุกตัวในผลลัพธ์
4. เรียงผลลัพธ์สุดท้าย

ตัวอย่างโค้ด

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))  # Output: ['a','a','ab','abc','abcb','b','b','ba','bc','bcba','cb','cba']

อินพุต

"abcba"

เอาต์พุต

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