在Python中查找所有子串的含有同字异序词的位置

假设有一个只包含小写字母的字符串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为从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']