字符串旋转

字符串旋转

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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
11-26 15:46
已编辑
字节国际 电商后端 24k-35k
点赞 评论 收藏
分享
评论
2
收藏
分享
牛客网
牛客企业服务