被想复杂的回环变位

今天看算法4发现有个问题很有意思,题目是这样的

如果字符串 s 中的字符循环移动任意位置之后能够得到另一个字符串 t,那么 s 就被称为 t 的回环变位(circular rotation)。例如,ACTGACG 就是 TGACGAC 的一个回环变位,反之亦然。判定这个条件在基因组序列的研究是很重要的。编写一个程序检查两个给定的字符串 s 和 t 是否互为回环变位。提示:答案只需要一行 indexOf(),length() 和字符串连接的代码。

我一开始看见这个题目是不是要几重循环来实现,这种思路是把每个都拆成单个字符。每个字符都在s里面查找位置,然后由key接收位置,然后在进行下一个字符查找,这个字符......然后试着用这种敲下代码看。敲到一半发现这个方法非常复杂。然后再看了题目,题目提示:一行用到indexOf、
然后想了下怎么可以用到一行就可以解决呢。边想边在纸上画由字符组成的环形。试着用电脑画了下,大概是这样的。

hh.png

从图中可以清晰的看出题目的意思,不管从哪个字符按顺序组成的字符串都可以是 s 的回环变位,反之亦然。如果给 s 字符串的中字符设置编号

0 1 2 3 4 5 6
A C T G A C G

如果按照上面的编号那么 t 字符串可以为

2 3 4 5 6 0 1
T G A C G A C

可以看出来两个都是有序的。这时候想到的方法是利用字符查找,由 字符串 t 的首个字符作为被搜索字符,在 s 中搜索,得到的位置由这个位置开始作为 s1 字符串的首字符,然后逐个拆开字符串 s 拼接 s1 中......中间省略各种心酸,最后利用此方法完成的代码如下,因为最新喜欢上了Python,所以使用Python来实现

# encoding: utf-8

"""
@author: ximens
@file: 20160719.py
@time: 2016/7/19 23:31
"""

def string(s, t):
    if len(s) != len(t):
        return False
    key = 0
    a = t[0:1]
    for x in t:
        key = key + s[key:].find(a)
        if (s[key:] + s[0:key]) == t:
            return True
        key += 1
    return False

s1 = "ACTGACG"
s2 = "TGACGAC"
print string(s2, s1)

俗话说万事开头难,确实如此,一看到这个问题就想的复杂无比。刚完成上面的代码不就之后又想到了一种更简洁的方法,代码更少。

# encoding: utf-8

"""
@author: ximens
@file: 20160719.py
@time: 2016/7/19 23:31
"""

def string(s, t):
    if (s+s).find(t) != -1:
        return True
    return False

s1 = "ACTGACG"
s2 = "TGACGAC"
print string(s1, s2)

因为 s+s 得到字符串包含了所有字符为开始组成的字符串,所以 字符串 t 只要可以在里面搜索到,那么就可以称为 s 是 t 的回环变位。