C++程序 检查字符串是否可以通过旋转另一个字符串2个位置获得
给定两个字符串,任务是找出一个字符串是否可以通过旋转另一个字符串两个位置而得到。
范例:
输入: string1 = “amazon”,string2 = “azonam”
输出: Yes
//旋转逆时针
输入: string1 =“amazon”,string2 =“onamaz”
输出: Yes
//旋转顺时针
1-只有两种情况:
a)顺时针旋转
b)逆时针旋转
2-如果是顺时针旋转,那么元素右移。
因此,检查字符串2的子字符串[2….len-1]与字符串2的子字符串[0,1]连接起来是否等于字符串1。
如果是,则返回true。
3-否则,检查它是逆时针旋转,即元素向左移动。
因此,检查子串[len-2,len-1]与子串[0….len-3]的组合是否使它等于字符串1。
然后返回true。
4-否则,返回false。
以下是上述方法的实现。
//C ++程序,检查字符串是否旋转两次另一个字符串。
#include
using namespace std;
//检查是否获得了string1
bool isRotated(string str1,
string str2)
{
if (str1.length()! = str2.length())
return false;
if(str1.length()<2){
return str1.compare(str2)== 0;
}
string clock_rot = "";
string anticlock_rot = "";
int len = str2.length();
//初始化为逆时针旋转
anticlock_rot = anticlock_rot +
str2.substr(len-2,2)+
str2.substr(0,len-2);
//初始化顺时针旋转
clock_rot = clock_rot +
str2.substr(2)+
str2.substr(0,2);
//检查它们是否等于string1
return(str1.compare(clock_rot)== 0 ||
str1.compare(anticlock_rot)== 0);
}
//驱动代码
int main()
{
string str1 = "geeks";
string str2 = "eksge";
isRotated(str1, str2)?cout <<“Yes”
:cout <<“No”;
返回0;
}
输出:
Yes
时间复杂度 :O(n),其中n是给定字符串的大小。