在 python 中递归计算字母字符串 s 和 t 共享的数量

Question

我必须递归地或通过列表理解计算两个给定字符串的 lingo 分数。两个字符串共有一个字母。

我试过这样做，但只有当 s[0] 在 t 中时它才有效，否则它不会做它应该做的事情，我看不出这里到底出了什么问题。

def count(e, L):
    lc = [1 for x in L if x == e]
    return sum(lc)

def lingo(s, t):
    if s == '' or t == '':
        return 0
    elif s == t:
        return len(s)
    if s[0] in t:
        lc = [count(s[x], t) for x in range(len(t))]
        return sum(lc)
    else:
        #remove s[0] and try again
        lingo(s[:1], t)

这些断言与赋值有关：

assert lingo('diner', 'proza') == 1
assert lingo('beeft', 'euvel') == 2
assert lingo('gattaca', 'aggtccaggcgc') == 5
assert lingo('gattaca', '') == 0

Answer 1

给你。这段代码是做什么的？如果其中一个字符串为空，return 0。其他情况下，它找到s[0]在s和t中出现的最小次数，然后我们使用递归计算最小出现次数t 版本中的 s[1] 没有第一个字符，依此类推。

def lingo(s, t):
    if s == '' or t == '':
        return 0
    return min(s.count(s[0]), t.count(s[0])) + lingo(s[1:], t.replace(s[0], ''))


assert lingo('diner', 'proza') == 1
assert lingo('beeft', 'euvel') == 2
assert lingo('gattaca', 'aggtccaggcgc') == 5
assert lingo('gattaca', '') == 0

Answer 2

最明显的错误

您在代码的最后一行缺少 return 语句。而不是：

    else:
        #remove s[0] and try again
        lingo(s[:1], t)

应该是：

    else:
        #remove s[0] and try again
        return lingo(s[:1], t)

代码冗余

您的以下代码是不必要的：

    elif s == t:
        return len(s)

虽然这个 return 是正确的结果，但它是一个特例，对一般情况没有特别帮助。在大多数情况下 s 和 t 是不同的；当它们相等时，计算它们共享字母数量的逻辑也应该有效。

算法逻辑错误

你的这行代码非常可疑：

lc = [count(s[x], t) for x in range(len(t))]

首先，x在t的长度范围内，但用作s的索引。如果 t 比 s 长，这将立即引发 IndexError 异常。如果 t 比 s 短或相同，那么它不会引发异常，但很可能 return 是错误的结果。

注意提供的这个有趣的测试用例：

assert lingo('beeft', 'euvel') == 2

字母'e'在'beeft'中出现两次，在'euvel'中出现两次，结果是2。但是如果你计算count(s[1], t) + count(s[2], t)，你会发现值4 .这是因为s的第一个'e'在t中找到了两次，s的第二个'e'也在[=19=中找到了两次].

提供了一种仔细修复此问题的方法。你需要了解min(s.count(s[0]), t.count(s[0])).

背后的逻辑

其他python解决方案

现在你绝对想使用递归和列表理解。如果您对解决问题的其他方法感兴趣，这里有不同的算法。

对字符串进行排序（排序是一种强大的工具，可以使许多问题变得简单）

def lingo(s, t):
  s = sorted(s) # this doesn't modify the original string, it makes a local copy
  t = sorted(t) # this doesn't modify the original string, it makes a local copy
  result = 0
  i = 0
  j = 0
  while (i < len(s) and j < len(t)):
    if s[i] == t[j]:
      result += 1
      i += 1
      j += 1
    elif s[i] < t[j]:
      i += 1
    else:
      j += 1
  return result

复杂度分析：排序需要N log N + M log M次操作，其中N=len(s)，M=len(t)。整个while循环只需要N+M次操作；之所以这么快，是因为 s 和 t 按相同的顺序排序，所以我们到达 s 的元素的时间与 t 中的相应元素相同，所以我们不需要将 s 的每个元素与 t 的每个元素进行比较.

collections.Counter（一个python对象，专门用于计算出现次数）

import collections
def lingo(s, t):
  return sum((collections.Counter(s) & collections.Counter(t)).values())

复杂性分析：这需要 N + M 次操作，其中 N=len(s) 和 M=len(t)。计数器简单地通过遍历 s 一次来统计 s 中每个字母的出现次数，以及遍历 t 一次来统计每个字母在 t 中出现的次数；然后 & 操作保留每个字母的两个计数中的最小值（让人想起 Janecx 的 min(...) 操作）；然后将所有计数相加。求和只需要与不同字母一样多的操作，在 DNA 序列的情况下是 4；在字母单词的情况下是 26；通常在 ASCII/Latin-1 字符串中最多为 256.

递归方法 来自复杂性分析：采用N * M 操作，其中 N=len(s) 和 M=len （吨）。这比其他两种方法慢得多，因为对于 s 的每个元素，我们都需要遍历 t 的每个元素；迭代编写，这将是一个嵌套在第二个 for 循环中的 for 循环。

在 python 中递归计算字母字符串 s 和 t 共享的数量

with recursion in python calculate the amount of letters strings s and t share

python

recursion

list-comprehension

最明显的错误

代码冗余

算法逻辑错误

其他python解决方案