LeetCode 题解工作台
统计包含给定前缀的字符串
给你一个字符串数组 words 和一个字符串 pref 。 返回 words 中以 pref 作为 前缀 的字符串的数目。 字符串 s 的 前缀 就是 s 的任一前导连续字符串。 示例 1： 输入： words = ["pay"," at tention","practice"," at tend"…
3
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·string
答案摘要
根据题目描述，我们遍历字符串数组 `words` 中的每个字符串 ，判断其是否以 作为前缀，如果是，则答案加一。 时间复杂度 $O(n \times m)$，空间复杂度 。其中 和 分别是字符串数组 `words` 和字符串 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·string 题型思路
题目描述
给你一个字符串数组 words 和一个字符串 pref 。
返回 words 中以 pref 作为 前缀 的字符串的数目。
字符串 s 的 前缀 就是 s 的任一前导连续字符串。
示例 1：
输入：words = ["pay","attention","practice","attend"], pref = "at"
输出：2
解释：以 "at" 作为前缀的字符串有两个，分别是："attention" 和 "attend" 。
示例 2：
输入：words = ["leetcode","win","loops","success"], pref = "code"
输出：0
解释：不存在以 "code" 作为前缀的字符串。
提示：
1 <= words.length <= 1001 <= words[i].length, pref.length <= 100words[i]和pref由小写英文字母组成
解题思路
方法一：一次遍历
根据题目描述，我们遍历字符串数组 words 中的每个字符串 ，判断其是否以 作为前缀，如果是，则答案加一。
时间复杂度 ，空间复杂度 。其中 和 分别是字符串数组 words 和字符串 的长度。
class Solution:
def prefixCount(self, words: List[str], pref: str) -> int:
return sum(w.startswith(pref) for w in words)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \cdot l + m) |
| 空间 | O(n \cdot l) |
面试官常问的追问
外企场景- question_mark
Check if the candidate can efficiently iterate over a list and perform string matching.
- question_mark
Assess if the candidate considers edge cases like empty strings or no matches.
- question_mark
Evaluate whether the candidate optimizes string matching appropriately for large inputs.
常见陷阱
外企场景- error
Failing to handle the case where the prefix is longer than the word.
- error
Not considering the empty string as a valid prefix.
- error
Inefficiently checking each character of the string when more efficient methods like startsWith() exist.
进阶变体
外企场景- arrow_right_alt
What if the prefix is empty?
- arrow_right_alt
What if words contain varying lengths?
- arrow_right_alt
Can the solution be optimized for larger arrays of words?