字符串ABCD,可以由字符串BCDA或者CDAB通过循环移位而得到。请编程实现以下检测:字符串S1是否可以由字符串S2通 过循环移位而得到。 语言不限(推荐C/C++,不推荐写伪码)

2 收藏


直接登录
最新评论
  • 人仨   2016/01/16

    把s1的第一个字符记录下来tmp=s1[0],然后在s2中找到tmp的位置pos,检查s2[pos]的左右是不是s1[1].如果都不是直接结束(无法通过循环得到)。如果s2[pos]的左方是s1[1],就循环比较,知道比较到s2[pos+1],同理比较右边。简单的想了一下,估计是最苯的方法了。感觉上应该有个递归可以用。

  • liuyezf   2016/01/16

    最简单粗暴的方法,把s1放进一个双向链表,然后带入s2去验证就ok。验证的关键其实就是判断各个字符前面和后面的字符是what。

  • 阿斌哥 硕士 2016/01/17

    常规写法如下,期待更好的解法
    int isCyclicShift(char a[], int aLen, char b[], int bLen) {
    int i, j, k;
    if(aLen<=0 || bLen<=0 || aLen!=bLen) {
    return 0;
    }
    for(i=0; i<bLen; i++) {
    if(b[i]==a[0]) {
    k = i;
    for(j=0; j<aLen; j++, k++) {
    if(a[j]!=b[k % bLen]) {
    break;
    }
    }
    if(j==aLen) {
    return 1;
    }
    }
    }
    return 0;
    }

  • singleon11   2016/01/20

    其实就是串匹配的问题。对S1进行构造,比如ABCD构造出ABCDABC作为主串,S2作为子串,使用KMP等串匹配算法即可。

    • 阿斌哥 硕士 2016/01/20

      kmp算法还没有深入学习过,不知道与上面解法相比,时间复杂度上是否更优?能否说一下与上面方法相比kmp算法哪些巧妙的步骤缩短了匹配的时间?

    • 超呆   2016/01/26

      构造匹配应该是最省心的方式了
      0)
      {
      echo $str0.”可以由字符串”.$str1.”通 过循环移位而得到”;
      }
      else
      {
      echo $str0.”不可以由字符串”.$str1.”通 过循环移位而得到”;
      }

      ?>

  • 奔跑的ksun 软件工程师 2016/01/20

    单链表A表示 S1
    循环链表B表示 S2
    循环检查A的节点对比B的节点,从头结点开始,如果一样2个链表继续指向下一个对比
    如果不一样,则把B头指针指向下一个,重新对比
    循环操作B的链表长度

  • mah0gany   2016/01/22

    “`python
    def foo(n, s1, s2):
    if n == 0:
    return False
    s1 = s1[1:] + 1[0]
    if s1 == s2:
    return True
    return foo(n-1, s1, s2)

    foo(len(s1), s1, s2)
    ““

  • 直接把S1,S2按字典序排序,然后strcmp(S1,S2)就行了吧…

  • s = s1 + s1;
    if(s.find(s2) != -1){
    index = s.find(s2);

    }

  • s = s1 + s1;
    if(s.find(s2) != -1){
    index = s.find(s2);
    temp = s.subStr(0, index) + s.substr(index+s1.length, s.length);
    if(temp == s1){
    return true;
    }
    }
    return false;