How do I check if a string is a substring of another string?

You can use the built-in `in` operator in Python, which checks if a substring exists within a string.

What is the best way to solve the 'Number of Strings That Appear as Substrings in Word' problem?

A simple solution would be to loop through each pattern and check if it's a substring of `word`. You can optimize this by avoiding redundant checks with a set or using a sliding window technique.

How does the sliding window technique work for substring matching?

A sliding window moves over the string to compare substrings of a fixed size with the target pattern, allowing efficient matching of segments in the word.

How do I handle identical patterns in the 'patterns' array?

You can avoid redundant checks by using a set to store previously matched substrings, or by using a dictionary to track the count of patterns already matched.

What is the time complexity of this problem?

The time complexity depends on the approach you choose: the naive method has O(n * m) complexity, while optimized methods such as sliding window can improve performance.

#1967

Easy

auto_awesome数组·string

LeetCode 题解工作台

作为子字符串出现在单词中的字符串数目

给你一个字符串数组 patterns 和一个字符串 word ，统计 patterns 中有多少个字符串是 word 的子字符串。返回字符串数目。子字符串是字符串中的一个连续字符序列。示例 1：输入： patterns = ["a","abc","bc","d"], word = "abc"…

数组字符串

题目描述

给你一个字符串数组 patterns 和一个字符串 word ，统计 patterns 中有多少个字符串是 word 的子字符串。返回字符串数目。

子字符串 是字符串中的一个连续字符序列。

示例 1：

输入：patterns = ["a","abc","bc","d"], word = "abc"
输出：3
解释：
- "a" 是 "abc" 的子字符串。
- "abc" 是 "abc" 的子字符串。
- "bc" 是 "abc" 的子字符串。
- "d" 不是 "abc" 的子字符串。
patterns 中有 3 个字符串作为子字符串出现在 word 中。

示例 2：

输入：patterns = ["a","b","c"], word = "aaaaabbbbb"
输出：2
解释：
- "a" 是 "aaaaabbbbb" 的子字符串。
- "b" 是 "aaaaabbbbb" 的子字符串。
- "c" 不是 "aaaaabbbbb" 的字符串。
patterns 中有 2 个字符串作为子字符串出现在 word 中。

示例 3：

输入：patterns = ["a","a","a"], word = "ab"
输出：3
解释：patterns 中的每个字符串都作为子字符串出现在 word "ab" 中。

提示：

1 <= patterns.length <= 100
1 <= patterns[i].length <= 100
1 <= word.length <= 100
patterns[i] 和 word 由小写英文字母组成

lightbulb

解题思路

方法一：模拟

遍历字符串数组 $\textit{patterns}$ 中的每个字符串 $p$ ，判断其是否为 $\textit{word}$ 的子字符串，如果是，答案加一。

遍历结束后，返回答案。

时间复杂度 $O(n \times m)$ ，空间复杂度 $O(1)$ 。其中 $n$ 和 $m$ 分别为 $\textit{patterns}$ 和 $\textit{word}$ 的长度。

1

2

3

4

class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        return sum(p in word for p in patterns)

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
The candidate is expected to demonstrate an understanding of string matching techniques.
question_mark
Evaluate if the candidate can handle edge cases where multiple identical patterns exist in the array.
question_mark
Pay attention to how the candidate chooses their approach in terms of complexity and efficiency.

warning

常见陷阱

外企场景

error
Failing to check for redundant patterns or using inefficient methods for substring matching.
error
Not considering edge cases where patterns might be of the same string repeated or very similar.
error
Overlooking the fact that every pattern should be checked individually without assuming overlap between patterns.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Test how the function handles an empty `patterns` array or an empty `word`.
arrow_right_alt
Try larger `patterns` arrays or longer words to see if the solution scales appropriately.
arrow_right_alt
Introduce mixed case inputs to assess how the candidate handles edge cases in substring checking.

help

常见问题

外企场景

继续练习

#1961 检查字符串是否为数组前缀 #1980 找出不同的二进制字符串 #1985 找出数组中的第 K 大整数