面試題 01.09. 字元串輪轉 : 字元串哈希運用題

題目描述

這是 LeetCode 上的 面試題 01.09. 字元串輪轉 ，難度為 簡單。

Tag : 「字元串哈希」

字元串輪轉。給定兩個字元串 ​

​s1​

​​ 和 ​

​s2​

​​，請編寫代碼檢查 ​

​s2​

​​ 是否為 ​

​s1​

​​ 旋轉而成（比如，​

​waterbottle​

​​ 是 ​

​erbottlewat​

​ 旋轉後的字元串）。

示例1:

輸入：s1 = "waterbottle", s2 = "erbottlewat"      

示例2:

輸入：s1 = "aa", s2 = "aba"      

提示：

• 字元串長度在

說明:

你能隻調用一次檢查子串的方法嗎？

字元串哈希

若兩字元串互為旋轉，則「其一字元串」必然為「另一字元串拓展兩倍長度後（循環子串）」的子串。

基于此，我們可以使用「字元串哈希」進行求解：先計算 ​

​s2​

​​ 的字元串哈希值 ​

​t​

​​，然後構造出 ​

​s1 + s1​

​​ 的哈希數組和次方數組，在兩數組中檢查是否存在長度為 的連續子段的哈希值 ​​

​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, 987654321
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(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      

• 時間複雜度：
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.面試題 01.09​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。