NeetCode #137LC-916MediumArrays & Hashing
← Back to All Problems#137 · #916 · Word Subsets(单词子集)
📌 Problem Statement & Constraints
A string
a is a subset of string b if every letter of a occurs in b at least as many times. Given words1 and words2, return every word in words1 that is a superset of every word in words2. Constraints: 1 <= words1.length, words2.length <= 10^4, 1 <= word length <= 10.💡 Core Algorithmic Approaches
- Being a superset of all words in
words2is equivalent to being a superset of their maximum character requirements. - Compute, for each character, the maximum count required across all words in
words2. Call this the requirement vector. - Then a word of
words1qualifies exactly when its character counts dominate the requirement vector. - This reduces the check from O(|words2|) per word to O(26) per word, which is the key optimisation.
💻 Benchmark Python3 Implementation
class Solution:
def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
need = [0] * 26
for b in words2:
cnt = [0] * 26
for ch in b:
cnt[ord(ch) - 97] += 1
for i in range(26):
need[i] = max(need[i], cnt[i]) # strongest requirement per letter
res = []
for a in words1:
cnt = [0] * 26
for ch in a:
cnt[ord(ch) - 97] += 1
if all(cnt[i] >= need[i] for i in range(26)):
res.append(a)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(total characters of words2 + 26 * |words1| + total characters of words1): the 26-length comparison per word is the dominant constant factor.
💾 Space Complexity
O(1): two 26-length arrays.
⚠️ Interview Pitfalls & Follow-ups
- Checking each word of
words2separately against each word ofwords1: O(|words1| * |words2| * 26), far too slow at 10^4 by 10^4. - Using the union of characters instead of the maximum counts: multiplicity matters, so
words2 = ["ee"]requires twoes. - Taking the sum of counts across
words2instead of the maximum: a letter required twice in one word and once in another needs a count of 2, not 3. - Forgetting that a word must dominate in every letter: the
all(...)over all 26 positions is essential.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.