字符串旋转
字符串旋转
http://www.nowcoder.com/questionTerminal/cb27a2cc0e8b41cbbdab7b0ca5c1bc23
字符串旋转
解析问题:对于输入字符串通过“;”拆分为字符串A和B。首先判断字符串A和B的长度是否相同,若不同直接输出flase,若相同进一步判断A是否可以通过旋转得到B:
暴力求解(一):
根据字符串A的长度L,通过循环从字符串下标1到L-2处拆分为两个字符串str1和str2,再将两者按照str2 str1的顺序组成新字符串A1与B进行比较,若A1与B相同,跳出循环输出true,若循环结束没有相同情况输出flase(通过一个标志变量判断是否提前退出循环)。
#include <bits/stdc++.h> using namespace std; int main(){ string s,A,B,A1,str1,str2; cin >> s; A = s.substr(0, s.find(';')); B = s.substr(s.find(';')+1,string::npos); if(A.length()!=B.length()) { cout<<"false"<<endl; return 0; } //标注变量判断是否提前退出循环 ,ture为提前退出循环,flase为正常结束循环 bool flag = false; for(int i=0;i<A.length()-1;i++){ str1 = A.substr(0, i); str2 = A.substr(i,string::npos); A1 = str2 + str1; if(A1== B){ flag = true; break; } } if(flag) cout<<"true"<<endl; else cout<<"false"<<endl; return 0; }
暴力求解优化(二):
在循环中,将字符串下标0到L-2处拆分为两个字符串str1和str2之前,判断拆分点处的字符与字符串B的首字符是否相同。若不相同拼接得到的字符串A1一定与B不相同,所以直接跳过本次拆分、拼接和比较过程,判断下一个拆分点。
#include <bits/stdc++.h> using namespace std; int main(){ string s,A,B,A1,str1,str2; cin >> s; A = s.substr(0, s.find(';')); B = s.substr(s.find(';')+1,string::npos); if(A.length()!=B.length()) { cout<<"false"<<endl; return 0; } //标注变量判断是否提前退出循环 ,ture为提前退出循环,flase为正常结束循环 bool flag = false; for(int i=0;i<A.length()-1;i++){ //判断拆分点处字符与字符串B首字符是否相等 if(A[i] != B[0]) continue; str1 = A.substr(0, i); str2 = A.substr(i,string::npos); A1 = str2 + str1; if(A1== B){ flag = true; break; } } if(flag) cout<<"true"<<endl; else cout<<"false"<<endl; return 0; }
最简方法(三):
将两个字符串A拼接为A1,判断A1字符串是否包含字符串B。例如
字符串A:youzan A1:youzanyouzan A1包含B:输出true
#include<iostream> using namespace std; int main() { string s; cin >> s; string A = s.substr(0, s.find(';')); string B = s.substr(s.find(';')+1,string::npos); if(A.length()!=B.length()) { cout<<"false"<<endl; return 0; } string A1=A+A; if(A1.find(B)!=string::npos) cout<<"true"<<endl; else cout<<"false"<<endl; return 0; }