字符串中的有效字符

Question

我得到一个字符串，如果有一个或多个无效字符，我必须 return False，否则为 True。需要注意的是，我只能使用内置函数和 str 操作（例如：in、+、indexing、len）和递归。到目前为止我所拥有的不起作用：

def is_valid_sequence(dna):
""" (str) -> bool

Return True if and only if the DNA sequence is valid
(A, T, C, and G)
:param dna: string sequence
:return: true or false
>>> is_valid_sequence('ATTAC')
True
>>> is_valid_sequence('FBSSS')
False
"""
valid_seq = 0

if len(dna) == 1 and dna in ['A', 'T', 'C', 'G']:
        valid_seq += 1
else:
    return is_valid_sequence(dna[1:])

显然，由于递归的原因，此代码无法运行，并且在下一次递归迭代后将 valid_seq 变量加 1 就被擦除。

Answer 1

正如其他人所说，您的递归函数在到达递归末尾时不会 return。你可以这样说：

if len(dna) == 1 and dna in ['A','T','G','C']:
    return True

也就是说，如果您知道 dna 字符串的长度始终大于或等于 1。总而言之，您可能会得到类似这样的结果：

def is_vaild_sequence(dna):
    if dna[0] not in ['A','T','G','C']:
        return False
    if len(dna) == 1:
        return True
    return is_vaild_sequence(dna[1:])

在这里，首先检查确定dna的第一个字符是否有效，然后是递归结构来检查整个序列。

理想情况下，如果这可以在不受递归约束的情况下解决，那就接受吧。迭代方法要好得多，即

for i in range(0,len(dna)):
    if dna[i] not in ['A','T','G','C']:
        return False
return True

Answer 2

对于较小的 DNA 序列（大约一千个字符），这是一个实用的实现

def is_valid_sequence (dna):
  # base case
  if len (dna) == 0:
    return True
  # check if first character is valid
  elif dna [0] not in ['A', 'T', 'C', 'G']:
    return False
  # otherwise, recurse on the rest of the characters
  else:
    return is_valid_sequence (dna [1:])

print (is_valid_sequence ('AATGCGA'))  # True
print (is_valid_sequence ('AATXGCGA')) # False

忠告

注意 python 中的递归 - 长 dna 字符串会导致堆栈溢出。尝试验证这个 "large" 的序列也会失败

GATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACA

您可以通过使用 Clojure 风格的 loop/recur 常量 space 递归机制 is_valid_sequence 实现 is_valid_sequence 来轻松避免这种情况

def recur (*values):
  return (recur, values)

def loop (f):
  acc = f ()
  while type (acc) is tuple and acc [0] is recur:
    acc = f (*acc [1])
  return acc

def is_valid_sequence (dna):
  # stack-safe loop/recur implementation
  # initialize loop state variable `s` to value of `dna`
  return loop (lambda s = dna:
    # base case
    True if len (s) == 0 else
    # check if first character valid
    False if s [0] not in ['A', 'T', 'C', 'G'] else
    # else recurse on the rest of the characters
    recur (s [1:]))

# does not overflow stack
print (is_valid_sequence ('GATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACA'))
# True

持续改进

loop/recur 实现提供了一个额外的机会来调整我们函数的性能。像我们对 dna[0] 和 dna[1:] 那样对字符串进行切片会在内存中创建 new 字符串；这是必要的，因为我们编写的第一个函数

中使用了递归 API

loop/recur 接口允许我们使用任何适合计算输出的数据类型——在这种情况下，一个简单的整数索引就可以了。词法作用域负责剩下的工作——dna 可以在我们的 lambda 中访问，不需要进行 dna[1:] 切片，这将为大输入 time/space 节省很多

def is_valid_sequence (dna):
  # only create this array once
  valid_chars = ['A', 'T', 'C', 'G']
  # initialize loop state variable `i` with 0
  return loop (lambda i = 0:
    True if len (dna) == i else
    False if dna [i] not in valid_chars else
    recur (i + 1))

Python 和不守规矩的 Lambda

注意我们是如何被迫在 lambda 中使用纯表达式而不是传统的 if/elif/else 语句语法——这对于简单的程序来说不是问题，但更复杂的程序可能很难用这种方式表达在 python.

这与上述程序的工作方式相同，但使用普通的旧函数而不是 lambda

def is_valid_sequence (dna):
  valid_chars = ['A', 'T', 'C', 'G']
  # plain old function; replaces lambda
  def myloop (i = 0):
    if len (dna) == 0:
      return True
    elif dna [i] not in valid_chars:
      return False
    else:
      return recur (i + 1)
  # use plain old function instead of lambda
  return loop (myloop)

字符串中的有效字符

Valid characters in a String

python

recursion

dna-sequence