leetcode 796. 旋转字符串

leetcode 796. 旋转字符串.

题目描述

796. 旋转字符串

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

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

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

示例 1:

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

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

提示:

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

解题思路

法1

方法1:连接+子串判断\

1. 连接s与s自己(s+=s)
2. 判断goal是否为连接后s的子串,因为如果是旋转字符串,那么就一定的两个连接s的子串

我们可以使用原生函数strings.Contains(s, goal)来判断goal字符串是否为s的子串

注意,要先判断s与goal是否相同,如果不同自己返回false

• 时间复杂度(O(n))时间复杂度：连接字符串 s 的操作需要 O(len(s)) 的时间复杂度，然后使用 strings.Contains 函数判断子串需要 O(len(s)) 的时间复杂度。因此，总体的时间复杂度为 O(len(s))。

• 空间复杂度(O(1))空间复杂度：在函数中没有使用额外的空间，只使用了常量级别的额外空间，因此空间复杂度为 O(1)。

执行结果

法1

s 和 goal。函数首先检查 s 和 goal 的长度是否相等，如果不相等，则无法通过旋转操作将 s 变为 goal，直接返回 false。

接下来，我们将 s 连接自身，形成一个新的字符串。然后使用 strings.Contains 函数判断 goal 是否为连接后的字符串的子串，如果是，则说明可以通过旋转操作将 s 变为 goal，返回 true；否则，返回 false。

func rotateString(s string, goal string) bool {
 if len(s) != len(goal) {
  return false
 }

 // 将s连接自身，判断goal是否为连接后的字符串的子串
 s += s
 return strings.Contains(s, goal)
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.8 MB , 在所有 Go 提交中击败了 71.08% 的用户 通过测试用例： 48 / 48 炫耀一下: