🌈个人首页: 神马都会亿点点的毛毛张
🕹️KMP算法练习题
文章目录
- 1.题目描述🍑
- 2.题解🫐
- 2.1 暴力解法🫒
- 2.2 模拟🥭
- 2.3 字符串匹配 - 移动匹配🥑
- 2.3.1 内置函数🥥
- 2.3.2 KMP🍊
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 s s和 g o a l goal goal的长度不一样,那么无论怎么旋转, s s s都不能得到 g o a l goal goal,返回 f a l s e false false。在长度一样(都为 n)的前提下,假设 s s s旋转 i i i位,则与 g o a l goal goal中的某一位字符$ goal[j] 对应的原 对应的原 对应的原s$中的字符应该为 s [ ( i + j ) m o d n ] s[(i+j)\ mod\ n] s[(i+j) mod n]。在固定 i i i的情况下,遍历所有 j j j,若对应字符都相同,则返回 t r u e true true。否则,继续遍历其他候选的 i i i。若所有的 i i i都不能使 s s s变成 g o a l goal goal,则返回 f a l s e false 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; // 返回前缀函数数组}
}
🌈欢迎和毛毛张一起探讨和交流!
联系方式参见个人主页: 神马都会亿点点的毛毛张