LeetCode 题解工作台
找出数组中的美丽下标 II
给你一个下标从 0 开始的字符串 s 、字符串 a 、字符串 b 和一个整数 k 。 如果下标 i 满足以下条件，则认为它是一个 美丽下标 ： 0 s[i..(i + a.length - 1)] == a 存在下标 j 使得： 0 s[j..(j + b.length - 1)] == b |j …
6
题型
4
代码语言
3
相关题
当前训练重点
困难 · 二分·搜索·答案·空间
答案摘要
class Solution: def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个下标从 0 开始的字符串 s 、字符串 a 、字符串 b 和一个整数 k 。
如果下标 i 满足以下条件，则认为它是一个 美丽下标 ：
0 <= i <= s.length - a.lengths[i..(i + a.length - 1)] == a- 存在下标
j使得：0 <= j <= s.length - b.lengths[j..(j + b.length - 1)] == b|j - i| <= k
以数组形式按 从小到大排序 返回美丽下标。
示例 1：
输入：s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15 输出：[16,33] 解释：存在 2 个美丽下标：[16,33]。 - 下标 16 是美丽下标，因为 s[16..17] == "my" ，且存在下标 4 ，满足 s[4..11] == "squirrel" 且 |16 - 4| <= 15 。 - 下标 33 是美丽下标，因为 s[33..34] == "my" ，且存在下标 18 ，满足 s[18..25] == "squirrel" 且 |33 - 18| <= 15 。 因此返回 [16,33] 作为结果。
示例 2：
输入：s = "abcd", a = "a", b = "a", k = 4 输出：[0] 解释：存在 1 个美丽下标：[0]。 - 下标 0 是美丽下标，因为 s[0..0] == "a" ，且存在下标 0 ，满足 s[0..0] == "a" 且 |0 - 0| <= 4 。 因此返回 [0] 作为结果。
提示：
1 <= k <= s.length <= 5 * 1051 <= a.length, b.length <= 5 * 105s、a、和b只包含小写英文字母。
解题思路
方法一
class Solution:
def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
def build_prefix_function(pattern):
prefix_function = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
while j > 0 and pattern[i] != pattern[j]:
j = prefix_function[j - 1]
if pattern[i] == pattern[j]:
j += 1
prefix_function[i] = j
return prefix_function
def kmp_search(pattern, text, prefix_function):
occurrences = []
j = 0
for i in range(len(text)):
while j > 0 and text[i] != pattern[j]:
j = prefix_function[j - 1]
if text[i] == pattern[j]:
j += 1
if j == len(pattern):
occurrences.append(i - j + 1)
j = prefix_function[j - 1]
return occurrences
prefix_a = build_prefix_function(a)
prefix_b = build_prefix_function(b)
resa = kmp_search(a, s, prefix_a)
resb = kmp_search(b, s, prefix_b)
res = []
print(resa, resb)
i = 0
j = 0
while i < len(resa):
while j < len(resb):
if abs(resb[j] - resa[i]) <= k:
res.append(resa[i])
break
elif j + 1 < len(resb) and abs(resb[j + 1] - resa[i]) < abs(
resb[j] - resa[i]
):
j += 1
else:
break
i += 1
return res
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate effectively uses binary search and string matching techniques.
- question_mark
The candidate demonstrates an understanding of how to optimize search space in large datasets.
- question_mark
The candidate chooses an efficient string matching algorithm based on input size constraints.
常见陷阱
外企场景- error
Not using binary search properly, leading to an inefficient solution.
- error
Choosing a naive string matching approach, causing timeouts for large inputs.
- error
Failing to consider edge cases where no beautiful indices exist, which could lead to incorrect results.
进阶变体
外企场景- arrow_right_alt
Consider variations where `k` is very large, and the efficiency of the algorithm is tested.
- arrow_right_alt
Extend the problem to handle multiple patterns for `a` and `b`.
- arrow_right_alt
Implement a solution that returns all beautiful indices within a given range instead of sorting them.