DNA序列

python解法

这道题目要理解清楚题意才行，不存在的最短DNA序列是什么？

例如，长度为2的序列包括：(AA, AG, AC, AT, CA, CC, CG, CT ……..)，要全部判断一遍才可以。并不是判断(AA, CC, GG TT)就可以了。

所以，要一层一层的判断，长度为1的所有子序列，长度为2的所有子序列……长度为n的所有子序列。有点像二叉树的层序遍历。

def calc(string):
    arr = ['']
    for i in range(0, len(string) + 1):
        tmpArr = []   # 下一层要判断的子序列。
        for item in arr:
            for char in ['A', 'C', 'G', 'T']:
                if item + char not in string:
                    return i + 1
                tmpArr.append(item + char)
        arr = tmpArr


print(calc(input()))

简单一些的思路，遍历一遍整个字符串，得到每个字符连续出现的次数的集合，例如a出现了[1,2,3,4],b出现了[1,2,4],c出现了[1,2,3,4,5],d出现了[1,2,3,4,5]
这四个集合里，都包含了1,2，但是没有包含3，所以最终应该返回3
a,b,c,d=[],[],[],[]
dna = str(input("输入dna："))

def forward(dna,i):
    x= dna[i]
    # print(i,x)
    while dna[i]==x :
        i=i+1
        if i==len(dna)-1:
            return i+1
    return i

def not_all_in(i,a,b,c,d):
    if (not i in a) or (not i in b) or (not i in c) or (not i in d):
        return True
    return False
i=0

while i<len(dna)-1:
    j = forward(dna,i)
    # print("现在在：",i,"j==",j)
    if dna[i]=="a":
        if 1 not in a:
            a.append(1)
        if j-i not in a:
            a.append(j-i)
        i = j
        # print("现在a:",a)
    elif dna[i]=="b":
        if 1 not in b:
            b.append(1)
        if j-i not in b:
            b.append(j-i)
        i = j
        # print("现在b:", b)
    elif dna[i] == "c":
        if 1 not in c:
            c.append(1)
        if j-i not in c:
            c.append(j-i)
        i = j
        # print("现在c:", c)
    else:
        if 1 not in d:
            d.append(1)
        if j-i not in d:
            d.append(j-i)
        i = j
        # print("现在d:", d)

print(a,b,c,d)

for i in range(1,len(dna)):
    if not_all_in(i,a,b,c,d):  print(i)