Giả sử chúng ta có một chuỗi s với các chữ cái thường. Chúng ta phải tìm tất cả trong s nơi phải có một chuỗi con khác trong s ở một vị trí khác là một phép đảo ngữ của chuỗi con đã lấy đó. Chúng ta phải tìm một danh sách các chuỗi con theo thứ tự từ vựng.
Vì vậy, nếu đầu vào là s ="abcba", thì đầu ra sẽ là ['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba' , 'bc', 'bcba', 'cb', 'cba'] đối với mỗi chúng, chúng ta có thể tìm thấy các từ đảo ngữ khác nhau có trong chính chuỗi đó.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
res:=một danh sách mới
-
L:=kích thước của s
-
đối với tôi trong phạm vi từ 1 đến L, thực hiện
-
smap:=một từ điển trống và tất cả các giá trị đều thuộc loại danh sách
-
đối với j trong phạm vi 0 đến L - i, do
-
cs:=chuỗi con của s từ chỉ mục j đến j + i-1]
-
k:=string sau khi nối các mục của cs ở dạng đã sắp xếp
-
chèn cs vào cuối smap [k]
-
-
đối với mỗi khóa k và giá trị v trong smap, thực hiện
-
nếu kích thước của v> =2, thì
-
chèn các phần tử của v vào res
-
-
-
-
trả lại res sau khi sắp xếp
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
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']