LeetCode 面试题 01.09. 字符串轮转-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode 面试题 01.09. 字符串轮转。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目

字符串轮转。给定两个字符串 s1 和 s2，请编写代码检查 s2 是否为 s1 旋转而成（比如，waterbottle 是 erbottlewat 旋转后的字符串）。

点击此处跳转题目。

示例1:

输入：s1 = “waterbottle”, s2 = “erbottlewat”
输出：True

示例2:

输入：s1 = “aa”, s2 = “aba”
输出：False

提示：

字符串长度在[0, 100000]范围内。

说明:

你能只调用一次检查子串的方法吗？

二、C# 题解

可以将题目理解为从字符串内部切一刀换序重组，判断是否能变为原字符串。但按照该思路写复杂度为 $O(n^2)$ ，不是很理想，因此还是从字符入手。

使用双指针 i,j 从左向右分别指向 s1,s2。i 的任务是遍历 s1，查找 s2 在 s1 中的前缀；j 的任务是标识 s2 中前缀的位置，即 s2[0]~s2[j - 1] 为 s2 与 s1 相同的部分。

以 s1：bunana, s2：nabuna 为例，可以看出，s1：buna | na，s2：na | buna，s1 的后缀和 s2 的前缀想同，均为 na，算法的具体流程如下：

$\begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& \uparrow & & & & \\ & n & a & b & u & n & a & (s2)\\ j:& \uparrow & & & & \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& & \uparrow & & & \\ & n & a & b & u & n & a & (s2)\\ j:& \uparrow & & & & \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& & & \uparrow & & \\ & n & a & b & u & n & a & (s2)\\ j:& \uparrow & & & & \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& & & & \uparrow & \\ & n & a & b & u & n & a & (s2)\\ j:& & \uparrow & & & \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& & & & & \uparrow \\ & n & a & b & u & n & a & (s2)\\ j:& \uparrow & & & & \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& & & & & & \uparrow \\ & n & a & b & u & n & a & (s2)\\ j:& & \uparrow & & & \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} & b & u & n & a & n & a & (s1)\\ i:& & & & & & & \uparrow \\ & n & a & b & u & n & a & (s2)\\ j:& & & \uparrow & & \end{array}\\$

最终，i 指向 s1 的末尾，j 指向 s2 前缀的后一字符，即 s2 后缀的起始位置。文章来源地址https://www.toymoban.com/news/detail-670075.html

public class Solution {
    public bool IsFlipedString(string s1, string s2) {
        int l1 = s1.Length, l2 = s2.Length;

        if (l1 != l2) return false;  // 长度不相等直接否掉

        int i = 0, j = 0;            // 双指针，i 指 s1，j 指 s2

        while (i < l1) {             // 遍历 s1，寻找 s2 的前缀
            if (s1[i] == s2[j]) j++; // 如果字符相同，则 j 后移
            else {                   // 字符不同，则 i、j 回退
                i -= j;
                j = 0;
            }
            i++;                     // i 始终前进
        }

        i = 0;

        while (j < l2) {             // 检查 s2 后缀是否为 s1 前缀
            if (s1[i++] != s2[j++]) return false;
        }

        return true;
    }
}