广东科技网站建设,自己做网站大概多少钱,网业游戏,英文网站推广工作#x1f64b;大家好#xff01;我是毛毛张! #x1f308;个人首页#xff1a; 神马都会亿点点的毛毛张 #x1f579;️KMP算法练习题 LeetCode链接#xff1a;796. 旋转字符串 文章目录 1.题目描述#x1f351;2.题解#x1fad0;2.1 暴力解法#x1fad2;2.2 模拟… 大家好我是毛毛张! 个人首页 神马都会亿点点的毛毛张 ️KMP算法练习题 LeetCode链接796. 旋转字符串 文章目录 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 100s 和 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[(ij)\ mod\ n] s[(ij) 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。字符串 ss 包含了所有 s 可以通过旋转操作得到的字符串只需要检查 goal 是否为 ss 的子字符串即可。
2.3.1 内置函数
class Solution {public boolean rotateString(String s, String goal) {return s.length() goal.length() (ss).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; // 返回前缀函数数组}
} 都看到这了不妨一键三连再走吧 欢迎和毛毛张一起探讨和交流 联系方式参见个人主页 神马都会亿点点的毛毛张
