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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告