题目形容

这是 LeetCode 上的 面试题 01.09. 字符串轮转 ，难度为 简略。

Tag : 「字符串哈希」

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

示例1:

输出：s1 = "waterbottle", s2 = "erbottlewat"输入：True

示例2:

输出：s1 = "aa", s2 = "aba"输入：False

提醒：

  • 字符串长度在 $[0, 100000]$ 范畴内。

阐明:
你能只调用一次查看子串的办法吗？

字符串哈希

若两字符串互为旋转，则「其一字符串」必然为「另一字符串拓展两倍长度后（循环子串）」的子串。

基于此，咱们能够应用「字符串哈希」进行求解：先计算 s2 的字符串哈希值 t，而后结构出 s1 + s1 的哈希数组和次方数组，在两数组中查看是否存在长度为 $n$ 的间断子段的哈希值 cur 与 t 相等。

不理解字符串哈希的同学能够看前置 : 字符串哈希入门

一些细节：其余语言可能不像 Java 那样存在天然取模，可手动取模，对于自带高精度的语言若不取模会导致单次计算复杂度回升，会 TLE。

Java 代码：

class Solution {    static int N = 200010, P = 13131;    static int[] h = new int[N], p = new int[N];    public boolean isFlipedString(String s1, String s2) {        if (s1.length() != s2.length()) return false;        int n = s1.length();        for (int i = 1; i <= n; i++) h[i] = h[i - 1] * P + s2.charAt(i - 1);        int t = h[n]; // s2 hash        s1 = s1 + s1;        p[0] = 1;        for (int i = 1; i <= 2 * n; i++) {            h[i] = h[i - 1] * P + s1.charAt(i - 1);            p[i] = p[i - 1] * P;        }        for (int i = 1; i + n - 1 <= 2 * n; i++) {            int j = i + n - 1, cur = h[j] - h[i - 1] * p[j - i + 1];            if (cur == t) return true;        }        return false;    }}

Python 代码：

N, P, MOD = 200010, 13131, 987654321h, p = [0] * N, [1] * Nclass Solution:    def isFlipedString(self, s1: str, s2: str) -> bool:        if len(s1) != len(s2):            return False        if s1 == s2:            return True        n = len(s1)        for i in range(1, n + 1):            h[i] = (h[i - 1] * P + ord(s2[i - 1])) % MOD        t = h[n]        s1 = s1 + s1        for i in range(1, 2 * n + 1):            h[i] = (h[i - 1] * P + ord(s1[i - 1])) % MOD            p[i] = (p[i - 1] * P) % MOD        for i in range(1, n + 1):            j = i + n - 1            cur = (h[j] - h[i - 1] * p[j - i + 1]) % MOD            if cur == t:                return True        return False
  • 工夫复杂度：$O(n)$
  • 空间复杂度：$O(n)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.面试题 01.09 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地

本文由mdnice多平台公布