796. Rotate String

Problem

Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.

A shift on s consists of moving the leftmost character of s to the rightmost position.

For example, if s = "abcde", then it will be "bcdea" after one shift.

https://leetcode.com/problems/rotate-string/

Example 1:

Input: s = "abcde", goal = "cdeab"
Output: true

Example 2:

Input: s = "abcde", goal = "abced"
Output: false

Constraints:

1 <= s.length, goal.length <= 100
s and goal consist of lowercase English letters.

Test Cases

1 2	class Solution: def rotateString(self, s: str, goal: str) -> bool:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('s, goal, expected', [
    ("abcde", "cdeab", True),
    ("abcde", "abced", False),
])
class Test:
    def test_solution(self, s, goal, expected):
        sol = Solution()
        assert sol.rotateString(s, goal) == expected

Thoughts

先比较 s 和 goal，如果不相同则移位一次 s 再继续比较。不用真的移动，可以利用下标。

时间复杂度 O(n²)。

Code

solution.py

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        n = len(s)
        if n != len(goal):
            return False

        for r in range(n):
            for i in range(n):
                if goal[i] != s[i-r]:
                    break
            else:
                return True

        return False

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。