来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-string
题目
给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。s 的 旋转操作 就是将 s 最左边的字符移动到最右边。
- 例如, 若
s = 'abcde'，在旋转一次之后结果就是'bcdea' 。
提示:
-
1 <= s.length, goal.length <= 100
-
s 和 goal 由小写英文字母组成
思路
暴力
由于题目数据量不大，可以尝试所有的旋转次数。可以用i+j%n的形式模拟旋转效果而不用真正的去操作旋转。复杂度为$O(n^2)$。
优化
如果s可以通过旋转变成goal那么goal+goal中一定包含s，可以用字符串查找算法在$O(n)$时间内判断是否存在，例如KMP算法。
代码
暴力解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
bool rotateString(string s, string goal) {
int n = goal.size();
if (s.size() != n) {
return false;
}
for (int i = 0 ; i < n ; ++i) {
bool flag = true;
for (int j = 0 ; j < n ; ++j) {
if (s[(j+i)%n] != goal[j]) {
flag = false;
break;
}
}
if (flag) {
return true;
}
}
return false;
}
}
;
|
最优解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
public:
int strStr(string haystack, string needle) {
int m = haystack.size();
int n = needle.size();
if (m == 0 && n == 0) {
return 0;
}
if (m == 0) {
return -1;
}
if (n == 0) {
return 0;
}
vector<int> next(n,0);
for (int j = 0, i = 1 ; i < n ; ++i) {
while(needle[i] != needle[j] && j > 0) {
j = next[j-1];
}
if (needle[i] == needle[j]) {
++j;
}
next[i] = j;
}
for (int j = 0, i = 0 ; i < m ; ++i) {
while(haystack[i] != needle[j] && j > 0) {
j = next[j-1];
}
if (haystack[i] == needle[j]) {
++j;
}
if (j == n) {
return i-j+1;
}
}
return -1;
}
bool rotateString(string s, string goal) {
if (s.size() != goal.size()) {
return false;
}
return strStr(goal+goal,s) != -1;
}
}
;
|