diff options
-rw-r--r-- | compare_strings_freq_char.c | 59 | ||||
-rw-r--r-- | compare_strings_freq_char.py | 45 |
2 files changed, 104 insertions, 0 deletions
diff --git a/compare_strings_freq_char.c b/compare_strings_freq_char.c new file mode 100644 index 0000000..2005764 --- /dev/null +++ b/compare_strings_freq_char.c @@ -0,0 +1,59 @@ +// 1170. Compare Strings by Frequency of the Smallest Character +#include "leetcode.h" + +/* + * let the function 'f(s)' be the frequency of the lexicographically smallest + * character in a non empty string 's'. for example, if 's = dcce' then 'f(s) = + * 2' because the lexicographically smallest character is 'c', which has a + * frequency of 2. you are given an array of strings 'words' and another array + * of query strings 'queries'. for each query 'queries[i]', count the number of + * words in 'words' such that 'f(queries[i]) < f(w)' for each 'w' in 'words'. + * return an integer array 'answer' where each 'answer[i]' is the answer to the + * i'th query + */ + +int lex_freq(char *w) { + int *map = (int *)calloc('z' - 'a' + 1, sizeof(int)), res; + char smallest = 'z'; + for (int i = 0; w[i]; i++) { + map[w[i] - 'a']++; + smallest = fmin(smallest, w[i]); + } + res = map[smallest - 'a']; + free(map); + return res; +} + +int *numSmallerByFrequency(char **queries, int queriesSize, char **words, + int wordsSize, int *returnSize) { + int *word_freq = (int *)malloc(wordsSize * sizeof(int)); + int *ans = (int *)calloc(queriesSize, sizeof(int)), freq; + *returnSize = queriesSize; + for (int i = 0; i < wordsSize; i++) + word_freq[i] = lex_freq(words[i]); + for (int i = 0; i < queriesSize; i++) { + freq = lex_freq(queries[i]); + for (int j = 0; j < wordsSize; j++) + if (freq < word_freq[j]) + ans[i]++; + } + free(word_freq); + return ans; +} + +int main() { + char *q1[] = {"cbd"}, *q2[] = {"bbb", "cc"}; + char *w1[] = {"zaaaz"}, *w2[] = {"a", "aa", "aaa", "aaaa"}; + int rs1, rs2; + int *nsbf1 = numSmallerByFrequency((char **)q1, ARRAY_SIZE(q1), (char **)w1, + ARRAY_SIZE(w1), &rs1); + int *nsbf2 = numSmallerByFrequency((char **)q2, ARRAY_SIZE(q2), (char **)w2, + ARRAY_SIZE(w2), &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", nsbf1[i]); // expect: 1 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", nsbf2[i]); // expect: 1 2 + printf("\n"); + free(nsbf1), free(nsbf2); +} diff --git a/compare_strings_freq_char.py b/compare_strings_freq_char.py new file mode 100644 index 0000000..27a19f8 --- /dev/null +++ b/compare_strings_freq_char.py @@ -0,0 +1,45 @@ +# 1170. Compare Strings by Frequency of the Smallest Character + +""" +let the function 'f(s)' be the frequency of the lexicographically smallest +character in a non empty string 's'. for example, if 's = dcce' then 'f(s) = +2' because the lexicographically smallest character is 'c', which has a +frequency of 2. you are given an array of strings 'words' and another array +of query strings 'queries'. for each query 'queries[i]', count the number of +words in 'words' such that 'f(queries[i]) < f(w)' for each 'w' in 'words'. +return an integer array 'answer' where each 'answer[i]' is the answer to the +i'th query +""" + + +class Solution(object): + def f(self, s): + t = sorted(list(s))[0] + return s.count(t) + + def numSmallerByFrequency(self, queries, words): + """ + :type queries: List[str] + :type words: List[str] + :rtype: List[int] + """ + query = [self.f(i) for i in queries] + word = [self.f(i) for i in words] + map = [] + for i in query: + cnt = 0 + for j in word: + if j > i: + cnt += 1 + map.append(cnt) + return map + + +if __name__ == "__main__": + obj = Solution() + print(obj.numSmallerByFrequency(queries=["cbd"], words=["zaaaz"])) + print( + obj.numSmallerByFrequency( + queries=["bbb", "cc"], words=["a", "aa", "aaa", "aaaa"] + ) + ) |