CY-Left

LeetCode基本功底

[leetcode]Rotate String by c++

Rotate String 循环字符串

原题&翻译

We are given two strings, A and B.

给出两个字符串,A 和 B。

A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = ‘abcde’, then it will be ‘bcdea’ after one shift on A. Return True if and only if A can become B after some number of shifts on A.
将 A 做一个 shift 转换,将 A 最左边部分字符移动到最右边的位置。比如,A = ‘abcde’ 通过移动一个字符 a 可以变成 ‘bcdea’。返回字符串 B 是否由 A shift 转换而来。

例子 1:
输出: A = 'abcde', B = 'cdeab'
输出: true

例子 2:
输入: A = 'abcde', B = 'abced'
输出: false
  • A 和 B 限制长度为 100.

解题思路

弱智解法

就是两层循环,注意第二层循环的取余操作。

class Solution {
public:
    bool rotateString(string A, string B) {
        int ALen = A.length();
        int BLen = B.length();
        if(ALen != BLen) return false;
        for(int i=0;i<ALen;i++){
            int j=0;
            for(;j<BLen;j++){
                if(B[j] != A[(i+j)%ALen]) break;
            }
            if(j==BLen) return true;
        }
        return false;
    }
};

解法二

这里搬来一个别的算法,貌似是 O(n), 看起来很高大上,其实,反正比上面的强,这个 2ms,上面的 3 ms。

class Solution {
public:
    bool rotateString(string A, string B) {
        if(A.size() !=B.size())
            return false;
        int as = A.size();
        for(int i=0;i<as;++i){
            string temp = A.substr(i,as-i);
            temp.append(A.substr(0,i));
            if(temp == B)
                return true;
        }
        return false;
    }
};

焉得谖草?言树之背。

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=691