旋转字符串 | 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) {// 检查两个字符串的长度，如果长度不同，返回 falseif (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;// 如果当前旋转后的字符数组等于目标字符数组，返回 trueif (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)modn]$。在固定$i$的情况下，遍历所有$j$，若对应字符都相同，则返回$true$。否则，继续遍历其他候选的 $i$。若所有的$i$都不能使$s$变成$goal$，则返回 $false$

class Solution {public boolean rotateString(String s, String goal) {// 检查两个字符串的长度，如果不相等则返回 falseif (s.length() != goal.length()) return false;int len = s.length(); // 获取字符串 s 的长度// 遍历字符串 s 的每一个字符作为旋转的起始位置for (int i = 0; i < len; i++) {int j; // 初始化目标字符串 goal 的索引// 遍历目标字符串 goalfor (j = 0; j < len; j++) {// 通过模运算计算旋转后的字符在字符串 s 中的位置，并进行比较if (s.charAt((i + j) % len) != goal.charAt(j)) break; // 如果不匹配，跳出内层循环}// 如果 j 达到目标字符串的长度，表示完全匹配，返回 trueif (j == len) return true;}// 如果没有找到匹配，返回 falsereturn 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) {// 检查字符串的长度，如果不相等则返回 falseif (s.length() != goal.length()) return false;// 将字符串 s 进行拼接，以便于处理旋转情况s = s + s;// 生成目标字符串 goal 的前缀函数数组int[] next = getNext(goal); int j = 0; // 匹配指针，用于遍历目标字符串 goal// 遍历拼接后的字符串 sfor (int i = 0; i < s.length(); i++) {// 当前字符不匹配时，根据前缀函数回退 jwhile (j > 0 && s.charAt(i) != goal.charAt(j)) j = next[j - 1];if (s.charAt(i) == goal.charAt(j)) j++;// 如果字符匹配，增加 j// 如果 j 达到目标字符串的长度，表示完全匹配，返回 trueif (j == goal.length()) return true;}// 如果没有找到匹配，返回 falsereturn 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++) {// 当前字符不匹配时，回退前缀指针 jwhile (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; // 返回前缀函数数组}
}

---

都看到这了，不妨一键三连再走吧！

🌈欢迎和毛毛张一起探讨和交流！
联系方式参见个人主页： 神马都会亿点点的毛毛张

---