What is a prefix in the context of this problem?

A prefix is a substring that occurs at the beginning of the string. For example, 'abc' is a prefix of 'abcdef'.

How do I check if a word is a prefix of the given string?

You can use the built-in `startswith` method in Python, or compare the initial part of the string manually using slicing or iteration.

What if there are duplicate words in the list?

Each occurrence of a word, even if it repeats, should be counted as long as it is a prefix of the given string.

How can I optimize my solution for large inputs?

Consider using more efficient methods such as sorting or hashing to reduce unnecessary checks and speed up the process.

What is the expected time complexity for this problem?

The expected time complexity is O(n * m), where n is the number of words in the list and m is the maximum length of the words.

#2255

Easy

auto_awesome数组·string

LeetCode 题解工作台

统计是给定字符串前缀的字符串数目

给你一个字符串数组 words 和一个字符串 s ，其中 words[i] 和 s 只包含小写英文字母。请你返回 words 中是字符串 s 前缀的字符串数目。一个字符串的前缀是出现在字符串开头的子字符串。子字符串是一个字符串中的连续一段字符序列。示例 1：输入： word…

数组字符串

题目描述

给你一个字符串数组 words 和一个字符串 s ，其中 words[i] 和 s 只包含 小写英文字母 。

请你返回 words 中是字符串 s 前缀的 字符串数目 。

一个字符串的前缀是出现在字符串开头的子字符串。子字符串 是一个字符串中的连续一段字符序列。

示例 1：

输入：words = ["a","b","c","ab","bc","abc"], s = "abc"
输出：3
解释：
words 中是 s = "abc" 前缀的字符串为：
"a" ，"ab" 和 "abc" 。
所以 words 中是字符串 s 前缀的字符串数目为 3 。

示例 2：

输入：words = ["a","a"], s = "aa"
输出：2
解释：
两个字符串都是 s 的前缀。
注意，相同的字符串可能在 words 中出现多次，它们应该被计数多次。

提示：

1 <= words.length <= 1000
1 <= words[i].length, s.length <= 10
words[i] 和 s 只包含小写英文字母。

lightbulb

解题思路

方法一：遍历计数

我们直接遍历数组 $\textit{words}$ ，对于每个字符串 $w$ ，判断 $s$ 是否以 $w$ 为前缀，如果是则答案加一。

遍历结束后，返回答案即可。

时间复杂度 $O(m \times n)$ ，其中 $m$ 和 $n$ 分别是数组 $\textit{words}$ 的长度和字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def countPrefixes(self, words: List[str], s: str) -> int:
        return sum(s.startswith(w) for w in words)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate is expected to demonstrate familiarity with string manipulation techniques.
question_mark
Efficiency in handling edge cases such as duplicate words should be discussed.
question_mark
Candidates may be expected to propose optimizations or alternative solutions for larger input sizes.

warning

常见陷阱

外企场景

error
Forgetting to count duplicate words in the list.
error
Overcomplicating the solution by using complex algorithms for a simple problem.
error
Neglecting to account for edge cases such as an empty list or a word being exactly the same as `s`.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of using the `startswith` method, implement a manual comparison of the beginning substring.
arrow_right_alt
Consider a case where the list of words is very large, and explore optimized approaches like sorting or hashing.
arrow_right_alt
Extend the problem to check for prefixes of multiple target strings, not just one.

help

常见问题

外企场景

继续练习

#2246 相邻字符不同的最长路径 #2273 移除字母异位词后的结果数组 #2227 加密解密字符串