本文概述
- 建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
- C ++
- C
- Java
- python
- C#
- 的PHP
(例如, 给定s1 = ABCD且s2 = CDAB, 则返回true, 给定s1 = ABCD, 而s2 = ACBD时, 返回false)
算法：
areRotations(str1, str2)
1. Create a temp string and store concatenation of str1 tostr1 in temp.temp = str1.str12. If str2 is a substring of temp then str1 and str2 are rotations of each other.Example:str1 = "ABACD"str2 = "CDABA"temp = str1.str1 = "ABACDABACD"Since str2 is a substring of temp, str1 and str2 are rotations of each other.推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。C ++
// C++ program to check if two given strings
// are rotations ofeach other
# include <
bits/stdc++.h>
using namespace std;
/* Function checks if passed strings (str1
and str2) are rotations of each other */
bool areRotations(string str1, string str2)
{
/* Check if sizes of two strings are same */
if (str1.length() != str2.length())
return false ;
string temp = str1 + str1;
return (temp.find(str2) != string::npos);
}/* Driver program to test areRotations */
int main()
{
string str1 = "AACD" , str2 = "ACDA" ;
if (areRotations(str1, str2))
printf ( "Strings are rotations of each other" );
else
printf ( "Strings are not rotations of each other" );
return 0;
}C
// C program to check if two given strings are rotations of
// each other
# include <
stdio.h>
# include <
string.h>
# include <
stdlib.h>
/* Function checks if passed strings (str1 and str2)
are rotations of each other */
int areRotations( char *str1, char *str2)
{
int size1= strlen (str1);
int size2= strlen (str2);
char *temp;
void *ptr;
/* Check if sizes of two strings are same */
if (size1 != size2)
return 0;
/* Create a temp string with value str1.str1 */
temp= ( char *) malloc ( sizeof ( char )*(size1*2 + 1));
temp[0] = '' ;
strcat (temp, str1);
strcat (temp, str1);
/* Now check if str2 is a substring of temp */
ptr = strstr (temp, str2);
free (temp);
// Free dynamically allocated memory/* strstr returns NULL if the second string is NOT a
substring of first string */
if (ptr != NULL)
return 1;
else
return 0;
}/* Driver program to test areRotations */
int main()
{
char *str1 = "AACD" ;
char *str2 = "ACDA" ;
if (areRotations(str1, str2))
printf ( "Strings are rotations of each other" );
else
printf ( "Strings are not rotations of each other" );
getchar ();
return 0;
}Java
// Java program to check if two given strings are rotations of
// each otherclass StringRotation
{
/* Function checks if passed strings (str1 and str2)
are rotations of each other */
static boolean areRotations(String str1, String str2)
{
// There lengths must be same and str2 must be
// a substring of str1 concatenated with str1.
return (str1.length() == str2.length()) &
&
((str1 + str1).indexOf(str2) != - 1 );
}// Driver method
public static void main (String[] args)
{
String str1 = "AACD" ;
String str2 = "ACDA" ;
if (areRotations(str1, str2))
System.out.println( "Strings are rotations of each other" );
else
System.out.printf( "Strings are not rotations of each other" );
}
}
// This code is contributed bymunjalpython
# Python program to check if strings are rotations of
# each other or not# Function checks if passed strings (str1 and str2)
# are rotations of each other
def areRotations(string1, string2):
size1 = len (string1)
size2 = len (string2)
temp = ''# Check if sizes of two strings are same
if size1 ! = size2:
return 0# Create a temp string with value str1.str1
temp = string1 + string1# Now check if str2 is a substring of temp
# string.count returns the number of occurrences of
# the second string in temp
if (temp.count(string2)>
0 ):
return 1
else :
return 0# Driver program to test the above function
string1 = "AACD"
string2 = "ACDA"if areRotations(string1, string2):
print "Strings are rotations of each other"
else :
print "Strings are not rotations of each other"# This code is contributed by Bhavya JainC#
// C# program to check if two given strings
// are rotations of each other
using System;
class GFG {/* Function checks if passed strings
(str1 and str2) are rotations of
each other */
static bool areRotations(String str1, String str2)
{// There lengths must be same and
// str2 must be a substring of
// str1 concatenated with str1.
return (str1.Length == str2.Length )
&
&
((str1 + str1).IndexOf(str2)
!= -1);
}// Driver method
public static void Main ()
{
String str1 = "FGABCDE" ;
String str2 = "ABCDEFG" ;
if (areRotations(str1, str2))
Console.Write( "Strings are"
+ " rotation s of each other" );
else
Console.Write( "Strings are "
+ "not rotations of each other" );
}
}// This code is contributed by nitin mittal.的PHP
<
?php
// Php program to check if
// two given strings are
// rotations of each other/* Function checks if passed
strings (str1 and str2) are
rotations of each other */
function areRotations( $str1 , $str2 )
{
/* Check if sizes of two
strings are same */
if ( strlen ( $str1 ) != strlen ( $str2 ))
{
return false;
}$temp = $str1 + $str1 ;
if ( $temp . count ( $str2 )>
0)
{
return true;
}
else
{
return false;
}
}// Driver code
$str1 = "AACD" ;
$str2 = "ACDA" ;
if (areRotations( $str1 , $str2 ))
{
echo "Strings are rotations " .
"of each other" ;
}
else
{
echo "Strings are not " .
"rotations of each other" ;
}// This code is contributed
// by Shivi_Aggarwal.
?>
输出如下：
Strings are rotations of each other使用的库函数：
strstr：
strstr在字符串中找到一个子字符串。
原型：char * strstr(const char * s1, const char * s2);
看到
http://www.lix.polytechnique.fr/Labo/Leo.Liberti/public/computing/prog/c/C/MAN/strstr.htm
更多细节
strcat：
strncat连接两个字符串
原型：char * strcat(char * dest, const char * src);
看到
http://www.lix.polytechnique.fr/Labo/Leo.Liberti/public/computing/prog/c/C/MAN/strcat.htm
更多细节
时间复杂度：
此问题的时间复杂度取决于strstr函数的实现。
【算法（一个检查字符串是否相互旋转的程序）】如果使用KMP匹配器执行strstr, 则上述程序的复杂度为(-)(n1 + n2), 其中n1和n2是字符串的长度。 KMP匹配器花费(-)(n)时间在长度为n的字符串中找到一个子字符串, 其中子字符串的长度假定小于该字符串。
推荐阅读
- 使用Java中的正则表达式获取字符串中每个单词的首字母
- 如何使用Python和其他语言为变量赋值
- JavaScript 严格模式解析和使用示例
- 5步骤简单处理XP系统响应速度慢
- 让xp文件下各种安全警告提示统统消失的妙招
- 让win xp系统定时关机的小妙招
- 迅速找到xp系统下bits服务的小攻略
- 让xp简单拥有win7任务栏的小妙招
- 调整显卡分辨率，让xp远离黑屏干扰!