Number of Strings That Appear as Substrings in Word — LeetCode 1967 Python Solution
EasyArrayString
- Problem
- #1967
- Pattern
- Hash Map
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given an array of strings patterns and a string word, return the number of strings in patterns that exist as a substring in word. A substring is a contiguous sequence of characters within a string.
Example
- Input
- patterns = ["a","abc","bc","d"], word = "abc"
- Output
- 3
- Explanation
- - "a" appears as a substring in "abc".
Python solution
Python
class Solution:
def numOfStrings(self, patterns: List[str], word: str) -> int:
return sum(p in word for p in patterns)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n \times m) |
| Space | O(1) auxiliary |
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1967. Number of Strings That Appear as Substrings in Word is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1967. Number of Strings That Appear as Substrings in Word?
- LeetCode 1967. Number of Strings That Appear as Substrings in Word is rated Easy on LeetCode.
- What is the time complexity of LeetCode 1967. Number of Strings That Appear as Substrings in Word?
- The Python solution on this page runs in O(n \times m).
- What is the space complexity of LeetCode 1967. Number of Strings That Appear as Substrings in Word?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1967. Number of Strings That Appear as Substrings in Word cover?
- LeetCode 1967. Number of Strings That Appear as Substrings in Word is tagged Array and String on LeetCode.