LeetCode796. 旋转字符串（从业务思想到算法思想）

LeetCode796. 旋转字符串（从业务思想到算法思想）

796. 旋转字符串（简单）

给定两个字符串, ​​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 和 goal 的长度不一样，那么无论怎么旋转，s 都不能得到 goal，返回 false。 然后根据业务开发思想，按要求旋转字符串，再做字符串是否相等的判断。

代码（Java）

/** * 方法一：暴力匹配 * 时间复杂度：O(n^2)，其中 n 是字符串 s 的长度。我们需要双重循环来判断。 * 空间复杂度：O(n)。拼接字符串的空间 */public boolean rotateString(String s, String goal) { int sLength = s.length(); int goalLength = goal.length(); if (sLength != goalLength) { return false; } for (int i = 0; i < sLength; i++) { char c = s.charAt(0); String substring = s.substring(1); s = substring + c; if (s.equals(goal)) { return true; } } return false;}

解法二：搜索子字符串

思路：

首先，一样的，如果 s 和 goal 的长度不一样，那么无论怎么旋转，s 都不能得到 goal，返回 false。

因为字符串 s+s 包含了所有 s 可以通过旋转操作得到的字符串，只需要检查goal 是否为 s + s 的子字符串即可。

代码（Java）

/** * 方法二：搜索子字符串 * 时间复杂度：O(n)，KMP算法搜索子字符串的时间复杂度为 O(n) * 空间复杂度：O(n)，KMP算法搜索子字符串的空间复杂度为 O(n) */public boolean rotateString2(String s, String goal) { return s.length() == goal.length() && (s + s).contains(goal);}

附：最优版KMP算法实现

public boolean rotateString3(String s, String goal) { return s.length() == goal.length() && knuthMorrisPrattMatch(s + s, goal) > -1;}/** * 剪枝的效果 * * @param s * @return */private int[] getNext(String s) { int len = s.length(), i = 0, j = -1; int[] next = new int[len]; next[0] = -1; while (i < len - 1) { if (j == -1 || s.charAt(i) == s.charAt(j)) { ++i; ++j; // 当两个字符相等时要跳过 if (s.charAt(i) == s.charAt(j)) { next[i] = next[j]; } else { next[i] = j; } } else { j = next[j]; } } return next;}/** * 字符串匹配，返回匹配的模式串在主串中的起始位置 * * @param sourceString 主串 * @param pattern 模式串 * @return */public int knuthMorrisPrattMatch(String sourceString, String pattern) { int sourceLen = sourceString.length(), patternLen = pattern.length(); int[] next = getNext(pattern); int i = 0, j = 0; while (i < sourceLen && j < patternLen) { // 当j为-1时，要移动的是i，当然j也要归0 if (j == -1 || pattern.charAt(j) == sourceString.charAt(i)) { j++; i++; } else { // i = i - j + 1; // i不需要回溯，j回到指定位置 j = next[j]; } } if (j == patternLen) { return i - j; } return -1;}}

​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。