旋转字符串 | LeetCode-796 | 模拟 | KMP | 字符串匹配

KMP算法练习题

---

LeetCode链接：796. 旋转字符串

---

1.题目描述

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

2.题解

2.1 暴力解法

class Solution {
    public boolean rotateString(String s, String goal) {
        // 检查两个字符串的长度，如果长度不同，返回 false
        if (s.length() != goal.length()) return false;
        
        char[] chs = s.toCharArray();// 将字符串 s 转换为字符数组
        char[] cht = goal.toCharArray();// 将目标字符串 goal 转换为字符数组
        
        // 遍历每一个可能的旋转位置
        for (int i = 0; i < chs.length; i++) {
            // 保存当前字符，以便进行旋转
            char temp = chs[0];
            // 将字符数组向左旋转一位
            for (int j = 0; j < cht.length - 1; j++) {
                chs[j] = chs[j + 1];
            }
            // 将保存的字符放到数组末尾
            chs[chs.length - 1] = temp;
            // 如果当前旋转后的字符数组等于目标字符数组，返回 true
            if (Arrays.equals(chs, cht)) return true;
        }
        
        return false;// 如果没有找到任何匹配，返回 false
    }
}

2.2 模拟

• 上面我们是通过将字符串转换成字符数组，然后实际进行旋转，当时实际上并不需要，我们可以通过取模的方式来模拟旋转字符串，这种方法称为模拟
• 首先，如果$s$和$goal$的长度不一样，那么无论怎么旋转，$s$都不能得到$goal$，返回$false$。在长度一样（都为 n）的前提下，假设$s$旋转$i$位，则与$goal$中的某一位字符$ goal[j] $对应的原$s$中的字符应该为 $s[(i+j)\ mod\ n]$。在固定$i$的情况下，遍历所有$j$，若对应字符都相同，则返回$true$。否则，继续遍历其他候选的 $i$。若所有的$i$都不能使$s$变成$goal$，则返回 $false$

class Solution {
    public boolean rotateString(String s, String goal) {
        // 检查两个字符串的长度，如果不相等则返回 false
        if (s.length() != goal.length()) return false;

        int len = s.length(); // 获取字符串 s 的长度
        // 遍历字符串 s 的每一个字符作为旋转的起始位置
        for (int i = 0; i < len; i++) {
            int j; // 初始化目标字符串 goal 的索引
            // 遍历目标字符串 goal
            for (j = 0; j < len; j++) {
                // 通过模运算计算旋转后的字符在字符串 s 中的位置，并进行比较
                if (s.charAt((i + j) % len) != goal.charAt(j)) break; // 如果不匹配，跳出内层循环
            }
            // 如果 j 达到目标字符串的长度，表示完全匹配，返回 true
            if (j == len) return true;
        }
        // 如果没有找到匹配，返回 false
        return false;
    }
}

2.3 字符串匹配 - 移动匹配

• 首先，如果 s 和 goal 的长度不一样，那么无论怎么旋转，s 都不能得到 goal，返回 false。字符串 s+s 包含了所有 s 可以通过旋转操作得到的字符串，只需要检查 goal 是否为 s+s 的子字符串即可。

2.3.1 内置函数

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

2.3.2 KMP

class Solution {
    public boolean rotateString(String s, String goal) {
        // 检查字符串的长度，如果不相等则返回 false
        if (s.length() != goal.length()) return false;

        // 将字符串 s 进行拼接，以便于处理旋转情况
        s = s + s;
        // 生成目标字符串 goal 的前缀函数数组
        int[] next = getNext(goal); 

        int j = 0; // 匹配指针，用于遍历目标字符串 goal
        // 遍历拼接后的字符串 s
        for (int i = 0; i < s.length(); i++) {
            // 当前字符不匹配时，根据前缀函数回退 j
            while (j > 0 && s.charAt(i) != goal.charAt(j)) j = next[j - 1];
            if (s.charAt(i) == goal.charAt(j)) j++;// 如果字符匹配，增加 j
            // 如果 j 达到目标字符串的长度，表示完全匹配，返回 true
            if (j == goal.length()) return true;
        }

        // 如果没有找到匹配，返回 false
        return false;
    }

    // 生成目标字符串的前缀函数数组
    public int[] getNext(String s) {
        int n = s.length();
        int[] next = new int[n]; // 存储前缀函数的数组
        int j = 0; // 前缀指针
        next[0] = 0; // 第一个字符的前缀长度为0

        // 遍历字符串，生成前缀函数数组
        for (int i = 1; i < n; i++) {
            // 当前字符不匹配时，回退前缀指针 j
            while (j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];
            if (s.charAt(i) == s.charAt(j)) j++;// 如果字符匹配，前缀长度增加
            next[i] = j;// 记录前缀长度到 next 数组
        }
        return next; // 返回前缀函数数组
    }
}