今天看算法4发现有个问题很有意思,题目是这样的
如果字符串 s 中的字符循环移动任意位置之后能够得到另一个字符串 t,那么 s 就被称为 t 的回环变位(circular rotation)。例如,ACTGACG 就是 TGACGAC 的一个回环变位,反之亦然。判定这个条件在基因组序列的研究是很重要的。编写一个程序检查两个给定的字符串 s 和 t 是否互为回环变位。提示:答案只需要一行 indexOf(),length() 和字符串连接的代码。
我一开始看见这个题目是不是要几重循环来实现,这种思路是把每个都拆成单个字符。每个字符都在s里面查找位置,然后由key接收位置,然后在进行下一个字符查找,这个字符......然后试着用这种敲下代码看。敲到一半发现这个方法非常复杂。然后再看了题目,题目提示:一行用到indexOf、
然后想了下怎么可以用到一行就可以解决呢。边想边在纸上画由字符组成的环形。试着用电脑画了下,大概是这样的。
从图中可以清晰的看出题目的意思,不管从哪个字符按顺序组成的字符串都可以是 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 的回环变位。