每日OJ题_牛客_NC114旋转字符串_C++_Java

目录

牛客_NC114旋转字符串

题目解析

C++代码1模拟

C++代码2找规律

Java代码

牛客_NC114旋转字符串

旋转字符串_牛客题霸_牛客网

描述：

字符串旋转:

给定两字符串A和B，如果能将A从中间某个位置分割为左右两部分字符串（可以为空串），并将左边的字符串移动到右边字符串后面组成新的字符串可以变为字符串B时返回true。

例如：如果A=‘youzan’，B=‘zanyou’，A按‘you’‘zan’切割换位后得到‘zanyou’和B相同，返回true。

再如：如果A=‘abcd’，B=‘abcd’，A切成‘abcd’和''（空串），换位后可以得到B，返回true。

数据范围：A,B字符串长度满足 n≤1000n≤1000，保证字符串中仅包含小写英文字母和阿拉伯数字

进阶： 时间复杂度 O(n)，空间复杂度 O(n)

题目解析

• 第一种解法：按照题目的要求模拟，每次旋转⼀下 A 字符串，看看是否和 B 字符串相同。
• 第二种解法：需要找到字符串旋转之后能匹配所满足的性质。如果 A 字符串能够旋转之后得到 B 字符串的话，在 A 字符串倍增之后的新串中，⼀定是可以找到B 字符串的。因此仅需让 A 字符串倍增，然后查找 B 字符串即可。

C++代码1模拟

class Solution {
public:
    bool solve(string A, string B) {
        for(int i = 1; i <= A.size(); ++i)
        {
            string tmp1 = A.substr(0, i);
            string tmp2 = A.substr(i, A.size());
            if(tmp2 + tmp1 == B)
                return true;
        }
        return false;
    }
};

C++代码2找规律

class Solution {
public:
    bool solve(string A, string B) {
        if(A.size() != B.size())
            return false;
        return (A + A).find(B) != -1;
    }
};

Java代码

import java.util.*;
public class Solution
{
    public boolean solve (String A, String B) 
    {
        if(A.length() != B.length())
            return false;
        return (A + A).contains(B);
    }
}