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

分手后的思念是犯贱 2023-09-29 07:23 25阅读 0赞

### 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);
    }

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_17_color_FFFFFF_t_70_g_se_x_16]

### 附：最优版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;
    }
    }

KMP算法参考文章：[https://blog.csdn.net/weixin\_52622200/article/details/110563434][https_blog.csdn.net_weixin_52622200_article_details_110563434]

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_17_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/23fbf120d9f8445a8df1bd7c9b6f9108.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_17,color_FFFFFF,t_70,g_se,x_16
[https_blog.csdn.net_weixin_52622200_article_details_110563434]: https://blog.csdn.net/weixin_52622200/article/details/110563434