https://leetcode.com/problems/word-subsets/description/?envType=daily-question&envId=2025-01-10
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.
String 가지고 노는 문제인듯 하다.
이런 유형의 문제 좀 다뤄봤으니 대강 읽고 얼른 풀어보자.
1. Python
좀 핵조잡스럽게 푼 거 같은데 그래도 어찌어찌 코드는 돌아간다.
Python이 제공하는 잡다한 Method들을 다 썼다 ㅎㅎ
class Solution:
def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
dic = {}
for x in words2 :
for ch in x :
if ch not in dic:
dic[ch] = 1
else:
cnt = x.count(ch)
dic[ch] = max(dic[ch],cnt)
ans = []
for y in words1 :
cond = True
for ch,cnt in dic.items():
if ch not in y or y.count(ch) < cnt:
cond = False
break
if cond : ans.append(y)
return ans
뭔가 Python의 collection에 있는 count 기능을 쓰면 좀 더 쉬울 거 같아서 Thinking...
근데 생각해보니 또 막상 크게 쓸 데는 없어서 일단 간단하게나마 적용시켜봤다. 코드는 잘 PASS되긴 한다.
class Solution:
def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
dic = {}
for x in words2 :
for ch in x :
if ch not in dic:
dic[ch] = 1
else:
cnt = x.count(ch)
dic[ch] = max(dic[ch],cnt)
ans = []
for y in words1 :
count = Counter(y)
cond = True
for ch,cnt in dic.items():
if ch not in count or cnt > count[ch]:
cond = False
break
if cond : ans.append(y)
return ans
굉장히 조잡스럽지만 C로 풀어보기
2. C
// 넘 조잡스러워서 포기.........
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
// Helper function to calculate character frequencies
void calculateFrequency(const char* word, int* freq) {
for (int i = 0; i < strlen(word); i++) {
freq[word[i] - 'a']++;
}
}
// Helper function to check if a word satisfies the universal condition
bool isUniversal(const char* word, int* condition) {
int freq[26] = {0};
calculateFrequency(word, freq);
for (int i = 0; i < 26; i++) {
if (freq[i] < condition[i]) {
return false;
}
}
return true;
}
// Main function
char** wordSubsets(char** words1, int words1Size, char** words2, int words2Size, int* returnSize) {
// Step 1: Create the universal condition array
int condition[26] = {0};
for (int i = 0; i < words2Size; i++) {
int tempFreq[26] = {0};
calculateFrequency(words2[i], tempFreq);
for (int j = 0; j < 26; j++) {
if (tempFreq[j] > condition[j]) {
condition[j] = tempFreq[j];
}
}
}
// Step 2: Check each word in words1 against the condition
char** result = (char**)malloc(words1Size * sizeof(char*));
int count = 0;
for (int i = 0; i < words1Size; i++) {
if (isUniversal(words1[i], condition)) {
result[count] = (char*)malloc((strlen(words1[i]) + 1) * sizeof(char));
strcpy(result[count], words1[i]);
count++;
}
}
// Step 3: Set the return size and return the result
*returnSize = count;
return result;
}