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

题目-检验子字符串

检验是否为另一个字符串循环移动后的子串。给定 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');

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

知识共享署名4.0国际许可协议,转载请保留出处; 部分内容来自网络,若有侵权请联系我:前端学堂 » 检验是否为另一个字符串循环移动后的子串

赞 (2) 打赏

评论 0

如果对您有帮助,别忘了打赏一下宝宝哦!

支付宝扫一扫打赏

微信扫一扫打赏