Word Subsets Python Solution with Tests

LeetCode 916, Medium. Topics: Array, Hash Table, String. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

lcpy gen -n 916   # by problem number
lcpy gen -s word_subsets   # by problem name

Problem

You are given two string arrays <code>words1</code> and <code>words2</code>. A string <code>b</code> is a subset of string <code>a</code> if every letter in <code>b</code> occurs in <code>a</code> including multiplicity. <ul> <li>For example, <code>“wrr”</code> is a subset of <code>“warrior”</code> but is not a subset of <code>“world”</code>.</li> </ul> A string <code>a</code> from <code>words1</code> is universal if for every string <code>b</code> in <code>words2</code>, <code>b</code> is a subset of <code>a</code>. Return an array of all the universal strings in <code>words1</code>. You may return the answer in any order.

Examples

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","o"]
Output: ["google","leetcode"]

Constraints

1 <= words1.length, words2.length <= 10^4
1 <= words1[i].length, words2[i].length <= 10
words1[i] and words2[i] consist only of lowercase English letters.
All the strings of words1 are unique.

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import Counter


class Solution:
    # Time: O(w1 * avg_len + w2 * avg_len)
    # Space: O(1)
    def word_subsets(self, words1: list[str], words2: list[str]) -> list[str]:
        need = Counter()
        for word in words2:
            counts = Counter(word)
            for letter, count in counts.items():
                need[letter] = max(need[letter], count)
        return [word for word in words1 if not (need - Counter(word))]

Complexity

Time	Space
O(w1 * avg_len + w2 * avg_len)	O(1)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Word Subsets Python Solution with Tests

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags