现在的位置: 首页 > 综合 > 正文

编程之美3.1 扩展

2019年01月04日 ⁄ 综合 ⁄ 共 335字 ⁄ 字号 评论关闭

原问题:给定两字符串s1和s2,要求判定s2是否能被s1做循环移位得到的字符串包含

解法1:直接对s1作循环移位,再利用strstr()函数判断,效率较低

解法2:串接两个s1得到s1s1,从而判断s2是否s1s1的子字符串即可;用空间换时间

扩展:

1) 先直接判断s2是否s1的子串,是则返回true终止,不是继续2)

2) 不需要串接两个s1,只需要将必要的字段接到s1尾部即可

对s1从后向前作遍历,找到s2最后一个字符的位置p2,并查看s1((p2+s1.length-s2.length+1)%s1.length)是否为s2的首字母

是的话则将s1中从p2位置开始的字符串接至s1的尾部并判断s2是否为其子串,否则继续查找

如果到最后没有找到满足条件的位置p2,则返回false

抱歉!评论已关闭.