LeetCode 题解工作台
重复叠加字符串匹配
给定两个字符串 a 和 b ，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1 。 注意： 字符串 "abc" 重复叠加 0 次是 "" ，重复叠加 1 次是 "abc" ，重复叠加 2 次是 "abcabc" 。 示例 1： 输入： a =…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · string·结合·string·matching
答案摘要
class Solution: def repeatedStringMatch(self, a: str, b: str) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 string·结合·string·matching 题型思路
题目描述
给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。
示例 1：
输入：a = "abcd", b = "cdabcdab" 输出：3 解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。
示例 2：
输入：a = "a", b = "aa" 输出：2
示例 3：
输入：a = "a", b = "a" 输出：1
示例 4：
输入：a = "abc", b = "wxyz" 输出：-1
提示：
1 <= a.length <= 1041 <= b.length <= 104a和b由小写英文字母组成
解题思路
方法一
class Solution:
def repeatedStringMatch(self, a: str, b: str) -> int:
m, n = len(a), len(b)
ans = ceil(n / m)
t = [a] * ans
for _ in range(3):
if b in ''.join(t):
return ans
ans += 1
t.append(a)
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(M+N) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Ability to handle string manipulations and substring matching efficiently.
- question_mark
Proficiency in optimizing solutions for string-based problems with variable input sizes.
- question_mark
Understanding of complexity trade-offs in terms of time and space for string matching problems.
常见陷阱
外企场景- error
Not considering edge cases where b might be smaller than a or when it might take multiple repetitions to match.
- error
Misunderstanding the failure condition when it is impossible for b to be a substring of repeated a.
- error
Improper handling of large input sizes, leading to performance inefficiencies.
进阶变体
外企场景- arrow_right_alt
Modify the problem by restricting the maximum number of repetitions.
- arrow_right_alt
Allow for case-sensitive string matching to increase complexity.
- arrow_right_alt
Test with random large inputs to assess time performance more accurately.