⚡Flashcard Drill➔
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

  1. Being a superset of all words in words2 is equivalent to being a superset of their maximum character requirements.
  2. Compute, for each character, the maximum count required across all words in words2. Call this the requirement vector.
  3. Then a word of words1 qualifies exactly when its character counts dominate the requirement vector.
  4. 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 words2 separately against each word of words1: 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 two es.
  • Taking the sum of counts across words2 instead 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems