Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
👉 Mục tiêu: Mỗi ngày giải 1 bài LeetCode, kiên trì tạo thói quen, từng bước chinh phục các kỹ năng lập trình.
Link : https://leetcode.com/problems/word-subsets/description/?envType=daily-question&envId=2025-01-10
Mysolution: https://leetcode.com/problems/word-subsets/solutions/6257912/easy-wordsubsets-solution-beat-100
LeetCode Problem: 916. Word Subsets
Difficulty: Medium
Problem Statement
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.
Examples
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 <= 1041 <= words1[i].length, words2[i].length <= 10words1[i]andwords2[i]consist only of lowercase English letters.- All the strings of
words1are unique.
Intuition
Bài toán yêu cầu xác định các từ “universal” trong danh sách words1 thỏa mãn tất cả yêu cầu về tần suất xuất hiện của ký tự trong words2.
Ngay từ đầu, mình nghĩ rằng cách tiếp cận tốt nhất là tính toán yêu cầu về tần suất ký tự từ tất cả các từ trong words2, rồi kiểm tra từng từ trong words1 xem có thỏa mãn các yêu cầu đó hay không.
Approach
- Tiền xử lý
words2:- Đối với mỗi từ trong
words2, mình sẽ đếm tần suất xuất hiện của từng ký tự (‘a’ đến ‘z’). - Lưu lại yêu cầu tối đa cho từng ký tự vào mảng
max_cnt[26].
- Đối với mỗi từ trong
- Kiểm tra các từ trong
words1:- Với mỗi từ trong
words1, mình cũng đếm tần suất của các ký tự. - Sau đó so sánh tần suất của các ký tự trong từ đó với yêu cầu trong
max_cnt. Nếu từ đó thỏa mãn tất cả yêu cầu, mình sẽ thêm nó vào kết quả.
- Với mỗi từ trong
- Tối ưu hóa:
- Nhờ việc tiền xử lý các yêu cầu từ
words2vào một mảngmax_cnt, mình tránh được việc phải tính toán lại nhiều lần, giúp giải pháp hiệu quả hơn.
- Nhờ việc tiền xử lý các yêu cầu từ
Complexity
Thời gian:
$$O(L_2 + L_1 \cdot 26)$$
– \(L_2\): Tổng số ký tự trong tất cả các từ của `words2`.
– \(L_1\): Tổng số ký tự trong tất cả các từ của `words1`.
Với mỗi từ trong `words1`, mình chỉ cần duyệt qua các ký tự của từ đó và so sánh với mảng có độ dài cố định (26 ký tự).
Không gian:
$$O(26) = O(1)$$
Không gian chỉ cần cho các mảng đếm tần suất cố định (mảng `max_cnt` và mảng tạm thời cho mỗi từ).
Code
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
int max_cnt[26] = {0}; // Mảng lưu trữ yêu cầu tối đa về tần suất ký tự
// Bước 1: Tiền xử lý các từ trong words2 để tìm yêu cầu tối đa tần suất ký tự
for (string& word : words2) {
int cnt[26] = {0}; // Mảng đếm tạm thời cho từ hiện tại trong words2
for (char c : word) {
cnt[c - 'a']++;
max_cnt[c - 'a'] = max(max_cnt[c - 'a'], cnt[c - 'a']);
}
}
vector<string> ans; // Kết quả lưu các từ "universal"
// Bước 2: Kiểm tra từng từ trong words1
for (string& word : words1) {
int cnt[26] = {0}; // Mảng đếm tần suất cho từ hiện tại trong words1
for (char c : word) {
cnt[c - 'a']++;
}
// Bước 3: Kiểm tra xem từ này có thỏa mãn yêu cầu "universal" không
bool is_Universal = true;
for (int i = 0; i < 26; i++) {
if (cnt[i] < max_cnt[i]) { // Nếu không thỏa mãn yêu cầu tần suất ký tự
is_Universal = false;
break; // Không cần kiểm tra nữa, từ này không phải "universal"
}
}
if (is_Universal) {
ans.push_back(word); // Thêm từ vào kết quả nếu nó là "universal"
}
}
return ans; // Trả về danh sách các từ "universal"
}
};
Ví dụ sử dụng
int main() {
Solution solution;
vector<string> words1 = {"amazon", "apple", "facebook", "google", "leetcode"};
vector<string> words2 = {"e", "o"};
vector<string> result = solution.wordSubsets(words1, words2);
for (string& word : result) {
printf("%s\n", word.c_str());
}
return 0;
}
Kết quả ví dụ
facebook
google
leetcode
Cảm nhận
Cách này khá là đơn giản cài đặt cũng nhanh . Vậy là chúng ta đã hết Day 1 của daily leetcode challenge
hay qué
Good job!