比较两个字符串以查看它们是否为旋转

旋转表示通过将另一个字符串向右或向右移动一个字符串来创建一个字符串。例如abc和cab是旋转的，abcd和bacd不是旋转的。我写了下面的代码，但它没有通过最后一个测试用例（不知道它是什么）。谁能给我关于一些提示哪里出错或有任何更有效的算法：比较两个字符串以查看它们是否为旋转

int isLetterInWord(char c, char* word)//find first letter in the word which is equal to c 
    { 
     int len = strlen(word); 
     for(int i=0; i<len; ++i) 
     { 
      if(c==word[i]) 
       return i; 
     } 
     return -1; 
    } 

    int isRotation(char* word1, char* word2) 
//check if word1 and word2 are rotation. if so return 1 otherwise -1 
    { 
     if(word1 == NULL && word2 == NULL) 
      return 1; 
     int len1 = strlen(word1); 
     int len2 = strlen(word2); 
     if(len1!= len2) 
      return -1; 
     for(int i=0; i<len1; ++i) 
     { 
      int pos = isLetterInWord(word1[i], word2); 
      if(pos == -1) 
       return -1; 
      else 
      { 
       int p1 = i, p2 = pos; 
       int cnt=0; 
       while(cnt<len1) 
       { 
        if(word1[p1++]!=word2[p2++]) 
         break; 
        if(p1==len1)p1=0; 
        if(p2==len2)p2=0; 
        cnt++ 
       } 
       if(cnt==len1) 
        return 1; 
      } 
     } 
     return -1; 
    }

来源

2014-11-03 user3273554

提示：看看tes没有看到它是什么的情况。 – 2014-11-03 06:27:45

您不知道代码失败的测试用例，所以我认为它是用于编码竞争。错误可能在于阅读字符串进行比较，也许你遇到了一个尺寸限制或忘记了迎合空间。长字符串也有可能超时;您的解决方案不是最高效的。 – 2014-11-03 07:10:32

解决这个问题的另一种算法如下：可以说第一个字符串是str1，需要检查str2是否是str1的旋转。的算法如下：

concatanate str1 to str1. Lets call it str3. 
Now check whether str2 is a sub-string of str3. 
If str2 is sub-string of str3 then it is a rotation of str1 otherwise not.

请找查询字符串的旋转功能：

int Rotations(char *str1, char *str2) 
{ 
    int size1 = strlen(str1); 
    int size2 = strlen(str2); 
    char *temp; 
    void *ptr; 
    if (size1 != size2) 
    return 0; 
    temp = (char *)malloc(sizeof(char)*(size1*2 + 1)); 
    temp[0] = '\0'; 
    strcat(temp, str1); 
    strcat(temp, str1); 
    ptr = strstr(temp, str2); 
    free(temp); 
    if (ptr != NULL) 
    return 1; 
    else 
    return 0; 
}

来源

2014-11-03 06:35:33 Sarwan

不错的做法.. – twid 2014-11-03 07:29:47

if(word1==NULL&&word2==NULL)

这应该是

if(word1==NULL||word2==NULL)

不通过你的逻辑了。

来源

2014-11-03 06:29:58 ravi

-1

概述：查找第一个字符匹配串字符，然后在字符串进行XOR，直到最小长度字符串结束，这样就可以发现字符串是否是彼此的旋转字符串

前提条件： bo的长度个字符串相等，如已经如上所述答案

步骤1：所述第一串中查找两个字符串通知pos（位置）第一匹配炭炭。

第2步：现在执行异或第一个字符串从pos到第一个字符串的结尾，与第二个字符串具有相同长度的子字符串。

步骤3：如果结果XOR是0意味着匹配的字符串的第一部分匹配，并且继续进行，以匹配从第二剩余部分（子串），这是第一个字符的第一个字符串在pos-1为char，和substring从pos+1字符串结束的字符串，然后对它们执行相同的XOR，

第4步：如果然后退出匹配与sucess，如果不匹配，则查找下一个在第一个字符串匹配char，并重复从步骤2，直到达到第一个字符串的末尾

来源

2014-11-03 07:26:39 twid

xoring和检查零比如何比较字符比较好吗？尤其是因为xoring需要额外的字符串或回调。另外，如果效率低下的解决方案，OP已经有效。问题在于指出他的代码中未知的测试用例失败。 – 2014-11-03 07:33:58

Xor是逻辑运算，所以它在最短的CPU周期内执行 – twid 2014-11-03 07:42:00

'JPE'指令总是比'JPE'后面的'XOR'更快。 – Baldrickk 2014-11-03 10:26:44

比较两个字符串以查看它们是否为旋转

回答

相关问题