LeetCode_796_Rotate String

题目链接

• https://leetcode.cn/problems/rotate-string/

题目描述

给定两个字符串, 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 由小写英文字母组成

解题思路

模拟法

• 假设s旋转i位,则与goal中的某一位字符goal[j]对应原s中的字符应该为s[(i+j) % n]
• 在固定i的情况下,遍历所有的j,若对应字符都相同,则返回true

搜索子字符串

• Since each rotation operation moves the leftmost character to the rightmost,因此如果goal可由s经过多步旋转而来,那么goal必然会出现在s+s中

AC代码

模拟法

class Solution {
    
    public boolean rotateString(String s, String goal) {
    
        int lenS = s.length();
        int lenG = goal.length();
        if (lenS != lenG) {
    
            return false;
        }
        for (int i = 0; i < lenG; i++) {
    
            boolean flag = true;
            for (int j = 0; j < lenG; j++) {
    
                if (s.charAt((i + j) % lenG) != goal.charAt(j)) {
    
                    flag = false;
                    break;
                }
            }
            if (flag) {
    
                return true;
            }
        }
        return false;
    }
}

搜索子字符串

class Solution {
    
    public boolean rotateString(String s, String goal) {
    
        return s.length() == goal.length() && (s + s).contains(goal);
    }
}