916. Word Subsets

Medium (Trung bình) C++ 🔗 Xem trên LeetCode

📋 Đề Bài

You are given two string arrays words1 and words2.

A string b is a subset of string a if every letter in b occurs in a including multiplicity.

  • For example, "wrr" is a subset of "warrior" but is not a subset of "world".

A string a from words1 is universal if for every string b in words2, b is a subset of a.

Return an array of all the universal strings in words1. You may return the answer in any order.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= words1.length, words2.length <= 104
  • 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.

🧠 Thuật Toán & Kỹ Thuật

Hash Table (Bảng băm)String (Chuỗi)
⏱️ Thời gian O(n²)
💾 Không gian O(n)

💻 Lời Giải

C++ 0916-word-subsets.cpp 
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        unordered_map<char, int> words2_freq;
        
        for (const string& word : words2) {
            unordered_map<char, int> temp_freq;
            for (char c : word) {
                temp_freq[c]++;
                words2_freq[c] = max(words2_freq[c], temp_freq[c]);
            }
        }

        vector<string> result;
        
        for (const string& word : words1) {
            unordered_map<char, int> word_freq;
            for (char c : word) {
                word_freq[c]++;
            }

            bool is_universal = true;
            for (const auto& [ch, count] : words2_freq) {
                if (word_freq[ch] < count) {
                    is_universal = false;
                    break;
                }
            }

            if (is_universal) {
                result.push_back(word);
            }
        }
        
        return result;
    }
};