Python程序：将两个字符串分割成每个分区都形成异位词

假设我们有两个非空字符串 s 和 t，它们长度相同。我们需要将它们分割成子字符串，使得 s 和 t 的每个子字符串对具有相同的大小，并且它们互为异位词。现在找到切割索引，使其导致 s 和 t 的最大切割数。如果找不到结果，则返回空列表。

因此，如果输入类似于 s = "bowcattiger" t = "owbactietgr"，则输出将为 [0, 3, 5, 6, 10]，因为我们可以将字符串分割成 5 个分区，使得每个字符串互为异位词。s = ["bow", "ca", "t", "tige", "r"]，t = ["owb", "ac", "t", "ietg", "r"]

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

  • intervals := 一个新的列表
  • cs := 一个映射，包含 s 中存在的字符及其频率
  • ct := 一个映射，包含 t 中存在的字符及其频率
  • 如果 cs 与 ct 不相同，则
    • 返回一个新的列表
  • 对于 x 从 s 的大小 - 1 到 0，执行以下操作：
    • cs[s[x]] := cs[s[x]] - 1
    • ct[t[x]] := ct[t[x]] - 1
    • 如果 cs 与 ct 相同，则
      • 将 x 插入到 intervals 的末尾
  • 对列表 intervals 进行排序并返回

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

示例

 实时演示

from collections import Counter
class Solution:
   def solve(self, a, b):
      intervals = []
      ca = Counter(a)
      cb = Counter(b)
      if ca != cb:
         return []
      for x in reversed(range(len(a))):
            ca[a[x]] -= 1
            cb[b[x]] -= 1
            if ca == cb:
               intervals.append(x)
      return sorted(intervals)
ob = Solution()
s = "bowcattiger"
t = "owbactietgr"
print(ob.solve(s, t))

输入

"bowcattiger", "owbactietgr"

输出

[0, 3, 5, 6, 10]

更新于: 2020年10月5日

432 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告