Python 中特殊等价字符串的组

假设我们有一个名为 A 的字符串数组。对 S 的一次移动包括交换 S 的任意两个偶数索引字符，或任意两个奇数索引字符。

现在，如果在对 S 进行任意次数的移动后，S 与 T 相同，则两个字符串 S 和 T 是特殊等价的。因此，如果 S = "zzxy" 且 T = "xyzz" 是特殊等价的，因为我们可以进行如下移动："zzxy" 到 "xzzy" 到 "xyzz"，交换 S[0] 和 S[2]，然后交换 S[1] 和 S[3]。

现在，来自 A 的特殊等价字符串组是 A 的非空子集，使得 -

组中每对字符串都是特殊等价的，并且该组是尽可能大的（不存在不在该组中的字符串 S 使得 S 与该组中的每个字符串都特殊等价）。我们必须找到来自 A 的特殊等价字符串组的数量。

因此，如果输入类似于 ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]，则输出将为 3，因为一个组是 ["abcd", "cdab", "cbad"]，因为它们都是成对特殊等价的，并且其他字符串都不与这些字符串成对特殊等价。还有另外两个组。它们是 ["xyzz", "zzxy"] 和 ["zzyx"]。

为了解决这个问题，我们将遵循以下步骤 -

  • codes := 一个新的集合
  • 对于 A 中的每个单词，执行
    • code := 连接两个具有偶数位置索引的字符串和另一个具有奇数位置索引的字符串
    • 将 code 添加到 codes 中
  • 返回 codes 的大小

让我们看看以下实现以获得更好的理解 -

示例

 实时演示

class Solution:
   def numSpecialEquivGroups(self, A):
      codes = set()
      for word in A:
         code = ''.join(sorted(word[::2])) +''.join(sorted(word[1::2]))
         codes.add(code)
      return len(codes)
ob = Solution()
print(ob.numSpecialEquivGroups(["abcd","cdab","cbad","xyzz","zzxy","z
zyx"]))

输入

["abcd","cdab","cbad","xyzz","zzxy","zzyx"]

输出

3

更新于: 2020年7月4日

239 次浏览

启动你的 职业生涯

通过完成课程获得认证

开始
广告