这是悦乐书的第 317 次更新, 第 338 篇原创
在开始今天的算法题前, 说几句, 今天是世界读书日, 推荐两本书给大家,《终身成长》和《禅与摩托车维修艺术》, 值得好好阅读和反复阅读.
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 186 题 (顺位题号是 796). 给定两个字符串 A 和 B, 在 A 上进行移位操作, 规则是将 A 最左边的字符移动到最右边去. 例如, 如果 A ='abcde', 那么在 A 上移位一次后, 它将是'bcdea'. 当且仅当 A 在 A 上移位一定次数后可以变为 B 时返回 True. 例如:
输入: A ='abcde',B ='cdeab'
输出: true
输入: A ='abcde',B ='abced'
输出: false
注意: A 和 B 的长度最多为 100.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
暴力解法.
特殊情况: 如果 A 本身就和 B 相等, 直接返回 true, 不需要对 A 进行移位.
正常情况: 每次对 A 进行移位一次后得到新的字符串, 判断是否和 B 相等, 使用一个辅助方法来完成移位操作. 先将 A 转为字符数组 arr, 然后创建一个新的字符数组 arr2, 两字符数组长度一致, 遍历 arr(从第二个元素开始遍历) 中的元素, 添加进 arr2 中去 (从第一位开添加), 遍历结束后, 将 arr 的第一位元素赋值给 arr2 的最后一位元素, 返回以 arr2 为基础创建的新字符串, 判断是否和 B 相等.
- public boolean rotateString(String A, String B) {
- if (A.equals(B)) {
- return true;
- }
- int n = A.length();
- for (int i=0; i<n; i++) {
- A = rotate(A);
- if (A.equals(B)) {
- return true;
- }
- }
- return false;
- }
- /**
- * 对 A 进行移位, 将字符串第一个字符放到最后去
- * @param A
- * @return
- */
- public String rotate(String A) {
- int n = A.length();
- char[] arr = A.toCharArray();
- char[] arr2 = new char[n];
- int index = 0;
- for (int i=1; i<n; i++) {
- arr2[index++] = arr[i];
- }
- arr2[index] = arr[0];
- return new String(arr2);
- }
03 第二种解法
也可以使用字符串截取的方式来解题.
- public boolean rotateString2(String A, String B) {
- if (A.equals(B)) {
- return true;
- }
- int n = A.length();
- for (int i=0; i<n; i++) {
- A = A.substring(1, n) + A.substring(0, 1);
- if (A.equals(B)) {
- return true;
- }
- }
- return false;
- }
04 第三种解法
还可以一行代码搞定. 思路是子字符串查找, 如果 B 真的可以通过 A 移位几次后得到, 那么在连续两个 A 组成的字符串中, 肯定会存在一个子串等于 B. 以题目的示例 1 为例子, 字符串 "abcdeabcde" 中存在一个子串 "cdeab".
- public boolean rotateString3(String A, String B) {
- return A.equals(B) || (A.length() == B.length() && (A+A).indexOf(B)>= 0);
- }
05 第四种解法
还可以通过 KMP 算法来解, 此解法来自于官方. 传送门: https://leetcode.com/problems/rotate-string/solution/
- public boolean rotateString(String A, String B) {
- int N = A.length();
- if (N != B.length()) return false;
- if (N == 0) return true;
- //Compute shift table
- int[] shifts = new int[N+1];
- Arrays.fill(shifts, 1);
- int left = -1;
- for (int right = 0; right <N; ++right) {
- while (left>= 0 && (B.charAt(left) != B.charAt(right)))
- left -= shifts[left];
- shifts[right + 1] = right - left++;
- }
- //Find match of B in A+A
- int matchLen = 0;
- for (char c: (A+A).toCharArray()) {
- while (matchLen>= 0 && B.charAt(matchLen) != c)
- matchLen -= shifts[matchLen];
- if (++matchLen == N) return true;
- }
- return false;
- }
06 小结
算法专题目前已日更超过五个月, 算法题文章 186 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/4836c5e4d3f6