宫水三叶的刷题日记

V1

2022/09/29阅读:22主题:前端之巅同款

面试题 01.09. 字符串轮转 : 字符串哈希运用题

题目描述

这是 LeetCode 上的 面试题 01.09. 字符串轮转 ,难度为 简单

Tag : 「字符串哈希」

字符串轮转。给定两个字符串 s1s2,请编写代码检查 s2 是否为 s1 旋转而成(比如,waterbottleerbottlewat 旋转后的字符串)。

示例1:

输入:s1 = "waterbottle", s2 = "erbottlewat"

输出:True

示例2:

输入:s1 = "aa", s2 = "aba"

输出:False

提示:

  • 字符串长度在 范围内。

说明: 你能只调用一次检查子串的方法吗?

字符串哈希

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

基于此,我们可以使用「字符串哈希」进行求解:先计算 s2 的字符串哈希值 t,然后构造出 s1 + s1 的哈希数组和次方数组,在两数组中检查是否存在长度为 的连续子段的哈希值 curt 相等。

不了解字符串哈希的同学可以看前置🧀 : 字符串哈希入门

一些细节:其他语言可能不像 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 = 20001013131987654321
h, p = [0] * N, [1] * N
class 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(12 * 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
  • 时间复杂度:
  • 空间复杂度:

最后

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

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

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1