You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.
Return the number of consistent strings in the array words.
Example 1:
Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2
Explanation: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.
Example 2:
Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
Output: 7
Explanation: All strings are consistent.
Example 3:
Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
Output: 4
Explanation: Strings "cc", "acd", "ac", and "d" are consistent.
Constraints:
- 1 <= words.length <= 104
- 1 <= allowed.length <= 26
- 1 <= words[i].length <= 10
- The characters in allowed are distinct.
- words[i] and allowed contain only lowercase English letters.
1. Python
파이썬과 함께라면 이런 문제는 쉽게 푼다. thanks to various functions
근데 또 time limit 걸릴 까봐 set를 사용했다.
보통 이런 문제는 set / dictionary를 써서 search 시 hashing 속도를 빠르게 해야 한다.
class Solution:
def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
s= set()
for x in allowed :
s.add(x)
ans = 0
for word in words :
cond = True
for c in word :
if c not in s :
cond = False
break
if cond : ans+=1
return ans
별건 아니고 count를 이렇게 거꾸로 하는 case도 있다.
class Solution:
def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
char_set = set(allowed)
count = len(words)
for word in words:
for c in word:
if c not in char_set:
count -= 1
break
return count
2. C
댕복잡하다 진짜
애증의 C 언어
int countConsistentStrings(char * allowed, char ** words, int wordsSize){
int n = wordsSize;
int cnt = 0;
for(int i=0;i<n;i++){
char * temp = words[i];
bool cond = true;
for(int j=0;j<strlen(temp);j++){
bool found = false;
for(int k=0;k<strlen(allowed);k++){
if(temp[j]==allowed[k]){
found = true;
break;
}
}
if(!found){
cond = false;
break;
}
}
if(cond) cnt++;
}
return cnt;
}
C풀이 정석은 아래와 같다고 한다 bit mask 이용하기
#include <stdio.h>
#include <string.h>
int countConsistentStrings(char * allowed, char ** words, int wordsSize) {
int allowed_chars[26] = {0};
int count = 0;
// Create a bitmask for allowed characters
for (int i = 0; allowed[i] != '\0'; i++) {
allowed_chars[allowed[i] - 'a'] = 1;
}
// Check each word for consistency
for (int i = 0; i < wordsSize; i++) {
int consistent = 1;
for (int j = 0; words[i][j] != '\0'; j++) {
if (allowed_chars[words[i][j] - 'a'] == 0) {
consistent = 0;
break;
}
}
count += consistent;
}
return count;
}
int countConsistentStrings(char * allowed, char ** words, int wordsSize){
int n = wordsSize;
int cnt = 0;
for(int i=0;i<n;i++){
char * temp = words[i];
bool cond = true;
for(int j=0;j<strlen(temp);j++){
bool found = false;
for(int k=0;k<strlen(allowed);k++){
if(temp[j]==allowed[k]){
found = true;
break;
}
}
if(!found){
cond = false;
break;
}
}
if(cond) cnt++;
}
return cnt;
}
3. C++
break 사용에 주의하라.
GPT 사용을 경계하라..
class Solution {
public:
int countConsistentStrings(string allowed, vector<string>& words) {
int cnt = words.size();
for(string s : words){
for(char c : s){
if(allowed.find(c)==string::npos){
cnt--;
break;
}
}
}
return cnt;
}
};