编程之美“字符串移位包含的有关问题”的另一种解法

编程之美“字符串移位包含的问题”的另一种解法

编程之美是一本训练编程思维的好书，给程序设计者很多启发。

其中第三章第一个问题是这样的：

问题3.1:字符串移位包含的问题

给定两个字符串s1和s2,要求判定s2是否弄够被s1做循环移位(rotate)得到的字符串包含。例如，给定s1=AABCD和s2=CDAA,返回true;给定s1=ABCD和s2=ACBD,返回false.

书中给了两种方法。

解法一对s1进行循环移位，再进行字符串包含的判断，遍历所有可能性。此法直接，但是效率不高。

解法二注意到，对s1做循环移位所得的所有字符串都是字符串s1s1的子字符串，将问题转化成考察s2是否在s1s1中。尽管解法2效率提高了，但是却多占用了s1大小的空间。实际上，我们可以连这s1大小的空间也不用占，也就是，总结中的那个问题“我们能否更进一步，不需要申请过多新的空间，而同样解决这一问题”的答案是：Yes。

解法三

我们的想法是，在s1后面"虚拟"地接上一个s1，这个"虚拟的s1"并不占空间，但是仍然按照解法2的思路进行。那么，如何实现这个"虚拟的s1"呢？其实只要把s1的最后一个元素，再指回s1的第一个元素即可。这可以用取模运算实现。比如，元素s1[(d1+i) mod d1]其实就是那个“虚拟的s1”的第i个元素，这里 0<=i<=d1-1, d1是字符串s1的长度.

下面是解法三的Python代码（因为最近在看Python编程，就拿此来练手）

# 算法描述
# step 0.计算src的长度d0,des的长度d1；
# step 1.寻找des[0]在src中的位置。如果找到,记此位置为i,进入step 2;如果没找到，跳到step 4.
# step 2.从j=1到d1-1,依次比较des[j]和src[i+j mod d1]. 如果某次比较不相同，执行step3;如果一直相同，返回True；
# step 3.从src[i+1]开始寻找des[0]在src中的位置。如果找到,记此位置为i,进入step 2;如果没找到，跳到step 4.
# step 4.返回False

##src='AABBCD'
##des='CDAA'
src='ABCD'
des='ACBD'
d1=len(src)
d2=len(des)
#print((d1,d2))
def match():
    for i in range(d1):
        if des[0]==src[i]:
            for j in range(1,d2):
                if des[j]!=src[(i+j)%d1]:
                    break
            else:
                #loop complete with finding a match
                return True
    else:
        return False

在Python shell，运行match()即可。

解法三的优点：

1. 字符串长度较大时，效率依然较好；

2.不需要申请额外空间存储第二个s1

相信经过分析思考，此法是自然而然的！

编程之美“字符串移位包含的有关问题”的另一种解法

相关推荐