题目形容
这是 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, 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
- 工夫复杂度:$O(n)$
- 空间复杂度:$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No. 面试题 01.09
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。
在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布