字符串中的有效字符

Question

给我一个字符串，如果有一个或多个无效字符，则必须返回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

对于小尺寸（约一千个字符）的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字符串会导致堆栈溢出。尝试验证甚至这个“大”序列都将失败

GATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGAC

您可以通过is_valid_sequence使用Clojure样式loop/recur机制进行恒定空间递归来轻松避免这种情况

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:]创建
新的 字符串；这仅是必需的，因为在我们编写的第一个函数中使用了递归API

该loop/recur接口允许我们使用任何数据类型是适合我们的计算输出-
在这种情况下，一个简单的整数索引就行了。词法作用域处理剩下的dna事情–在我们的lambda中可以访问，并且不需要进行dna[1:]切片，这将为大量输入节省大量时间/空间

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)