Python 程式：查詢字串中所有存在其字母異位詞的子字串

假設我們有一個包含小寫字母的字串 s。我們需要找到 s 中的所有子字串，這些子字串在 s 中的其他位置必須存在另一個是其字母異位詞的子字串。我們需要找到 s 中按字典序排列的子字串列表。

因此，如果輸入類似於 s = "abcba"，則輸出將為 ['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba', 'bc', 'bcba', 'cb', 'cba']，因為對於每個子字串，我們都可以在字串本身中找到不同的字母異位詞。

為了解決這個問題，我們將遵循以下步驟：

  • res := 一個新的列表

  • L := s 的大小

  • 對於 i 從 1 到 L，執行以下操作：

    • smap := 一個空字典，所有值都是列表型別

    • 對於 j 從 0 到 L - i，執行以下操作：

      • cs := s 從索引 j 到 j + i-1 的子字串

      • k := 將 cs 中的元素按排序後的形式連線而成的字串

      • 將 cs 插入 smap[k] 的末尾

    • 對於 smap 中的每個鍵 k 和值 v，執行以下操作：

      • 如果 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']

更新於: 2021年10月11日

410 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告