796. 旋转字符串

给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。

s 的 旋转操作 就是将 s 最左边的字符移动到最右边。

  • 例如, 若 s = 'abcde'，在旋转一次之后结果就是'bcdea' 。

示例 1:

1
2
输入: s = "abcde", goal = "cdeab"
输出: true

示例 2:

1
2
输入: s = "abcde", goal = "abced"
输出: false

提示:

  • 1 <= s.length, goal.length <= 100
  • s 和 goal 由小写英文字母组成

题解：

由于每次旋转操作都是把最左侧的一个字符移动到最右侧，因此goal是由s从任意位置开始经过多步旋转而来的，而字符串s + s中包含了所有字符串s经过旋转而得到的字符串，那么满足条件的goal就一定会出现在s + s字符串中。

ps：在很多头尾相连的数组题目中也经常使用两倍数组的技巧。

代码如下：

1
2
3
public boolean rotateString(String s, String goal) {
    return s.length() == goal.length() && (s + s).contains(goal);
}
  • 时间复杂度：O(N)，KMP算法搜索子字符串的时间复杂度为O(N)。
  • 空间复杂度：O(N)，KMP算法搜索子字符串的空间复杂度为O(N)。