检验是否为另一个字符串循环移动后的子串

题目-检验子字符串 #

检验是否为另一个字符串循环移动后的子串。给定 s1 和 s2，请设计一种方法来检验 s2 是否为 s1 的循环移动后的字符串。

示例 #

s1 = apple;

• s2 = ppale; 返回false;
• s2 = leapp; 返回true;

分析 #

第一个想法是将给定字符串s1挨个字符做循环移动，然后判断和s2是否相等，相等就返回true，反之亦然。算下时间复杂度：o（n），但是每次循环需要构造新的字符串，空间复杂度略高。

第二个想法就是同样循环一次，设置两个指针，一个指向s1，一个指向s2，依次挨个比较，相同就同时向后移动一个位置，不同则s2指针归位，重新开始比较，如果s1指针移动到字符串末尾，那么归位重新开始。直到s2指针移动到末尾，退出。这个方法其实一样，时间复杂度：o（n），减少了空间复杂度。

还有没有其他方法？？？？？有的，我最后列出来，你自己想想看。

Just Try #

请你自动动手试一下：在线编程环境

想想有没有其他思路？

想想时间和空间复杂度，能否优化一下

真的做不到么？

let you think， think makes you happy!

参考答案 #

循环的方案 #

function algorithm(str){
  let [s1, s2] = str;
  let s1Arr = s1.split(""), k='';
  for(let i=0; i< s1.length;i++){
    k = s1Arr.pop()
    s1Arr.unshift(k)
    if(s1Arr.join("") == s2){
      return true
    }
  }
  return false
}
function main(...param) {
  console.show("参数：" + param, "结果：" + algorithm(param))
  testPerformance(algorithm, param)
}
main('apple','leapp');

指针方案 #

function algorithm(str){
  let [s1, s2] = str;
  let i=0, j=0, k = 0;
  while(j<s2.length && k<s1.length*2){
    k++;
    if(s1[i] == s2[j]){
      if(j==s2.length-1){
        return true;
      }
      i++;
      j++;
    }
    else{
      i++;
      j=0;
    }
    if(i>s1.length-1){
      i=0;
      if(j==0) j=s2.length;
    }
  }
  return false;
}
function main(...param) {
  console.show("参数：" + param, "结果：" + algorithm(param))
  testPerformance(algorithm, param)
}
main('apple','leapp');

拼接字符串 #

这个我知道是目前最简单的方法，把两个s1拼接在一起，然后判断s2是不是s1子串就好了。

function algorithm(str){
  let [s1, s2] = str;
  return (s1+s1).indexOf(s2) >= 0
}
function main(...param) {
  console.show("参数：" + param, "结果：" + algorithm(param))
  testPerformance(algorithm, param)
}
main('apple','leapp');

请你自动动手试一下：在线编程环境