สมมติว่าเรามีสตริง s ที่มีตัวพิมพ์เล็ก เราต้องหาทั้งหมดที่จะต้องมีสตริงย่อยอื่นใน s ที่ตำแหน่งอื่นซึ่งเป็นแอนนาแกรมของสตริงย่อยที่รับ เราต้องหารายการของสตริงย่อยตามลำดับพจนานุกรม
ดังนั้น หากอินพุตเป็น s ="abcba" ผลลัพธ์จะเป็น ['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba' , 'bc', 'bcba', 'cb', 'cba'] สำหรับแต่ละรายการ เราสามารถพบแอนนาแกรมที่แตกต่างกันในสตริงได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
res :=รายการใหม่
-
L :=ขนาด s
-
สำหรับผมอยู่ในช่วง 1 ถึง L ทำ
-
smap :=พจนานุกรมเปล่า และค่าทั้งหมดเป็นรายการประเภท
-
สำหรับ j ในช่วง 0 ถึง L - i ทำ
-
cs :=สตริงย่อยของ s จากดัชนี j ถึง j + i-1]
-
k :=string หลังจากเข้าร่วมรายการของ cs ในรูปแบบการเรียงลำดับ
-
แทรก cs ที่ส่วนท้ายของ smap[k]
-
-
สำหรับแต่ละคีย์ k และค่า v ใน smap ทำ
-
ถ้าขนาด v>=2 แล้ว
-
แทรกองค์ประกอบของ v ลงใน res
-
-
-
-
คืนค่า res หลังจากจัดเรียง
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
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))
อินพุต
"abcba"
ผลลัพธ์
['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba', 'bc', 'bcba', 'cb', 'cba']
