Python程序：查找最长异位词子序列的长度

假设我们有两个小写字符串 S 和 T，我们需要找到最长异位词子序列的长度。

因此，如果输入类似于 S = "helloworld"，T = "hellorld"，则输出将为 8

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

  • c := 一个新的映射，d := 一个新的映射

  • 对于范围从 0 到 a 的大小，执行以下操作

    • 如果 a[i] 在 c 中，则

      • c[a[i]] := c[a[i]] + 1

    • 否则，

      • c[a[i]] := 1

  • 对于范围从 0 到 b 的大小，执行以下操作

    • 如果 b[i] 在 d 中，则

      • d[b[i]] := d[b[i]] + 1

    • 否则，

      • d[b[i]] := 1

  • res := 0

  • 对于 c 中的每个字符 ch，执行以下操作

    • 如果 d[ch] > 0，则

      • res := res + c[ch] 和 d[ch] 的最小值

  • 返回 res

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

示例

 实时演示

class Solution:
   def solve(self, a, b):
      c, d = {}, {}
      for i in range(len(a)):
         if a[i] in c:
            c[a[i]] += 1
         else:
            c[a[i]] = 1
      for i in range(len(b)):
         if b[i] in d:
            d[b[i]] += 1
         else:
            d[b[i]] = 1
      res = 0
      for ch in c:
         if d.get(ch, 0) > 0:
            res += min(c[ch], d[ch])
         return res
ob = Solution()
S = "helloworld"
T = "hellorld"
print(ob.solve(S, T))

输入

S = "helloworld", T = "hellorld"

输出

1

更新于: 2020年10月10日

270 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告