|
| 1 | +// Source : https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/ |
| 2 | +// Author : Hao Chen |
| 3 | +// Date : 2019-10-01 |
| 4 | + |
| 5 | +/***************************************************************************************************** |
| 6 | + * |
| 7 | + * Let's define a function f(s) over a non-empty string s, which calculates the frequency of the |
| 8 | + * smallest character in s. For example, if s = "dcce" then f(s) = 2 because the smallest character is |
| 9 | + * "c" and its frequency is 2. |
| 10 | + * |
| 11 | + * Now, given string arrays queries and words, return an integer array answer, where each answer[i] is |
| 12 | + * the number of words such that f(queries[i]) < f(W), where W is a word in words. |
| 13 | + * |
| 14 | + * Example 1: |
| 15 | + * |
| 16 | + * Input: queries = ["cbd"], words = ["zaaaz"] |
| 17 | + * Output: [1] |
| 18 | + * Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz"). |
| 19 | + * |
| 20 | + * Example 2: |
| 21 | + * |
| 22 | + * Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"] |
| 23 | + * Output: [1,2] |
| 24 | + * Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and |
| 25 | + * f("aaaa") are both > f("cc"). |
| 26 | + * |
| 27 | + * Constraints: |
| 28 | + * |
| 29 | + * 1 <= queries.length <= 2000 |
| 30 | + * 1 <= words.length <= 2000 |
| 31 | + * 1 <= queries[i].length, words[i].length <= 10 |
| 32 | + * queries[i][j], words[i][j] are English lowercase letters. |
| 33 | + ******************************************************************************************************/ |
| 34 | + |
| 35 | +class Solution { |
| 36 | +public: |
| 37 | + vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) { |
| 38 | + cout << queries.size() << " : " << words.size() << endl; |
| 39 | + vector<int> freq; |
| 40 | + for (auto w : words) { |
| 41 | + freq.push_back(f(w)); |
| 42 | + } |
| 43 | + sort(freq.begin(), freq.end()); |
| 44 | + |
| 45 | + vector<int> result; |
| 46 | + for (auto q : queries) { |
| 47 | + result.push_back(binary_search(freq, f(q))); |
| 48 | + } |
| 49 | + return result; |
| 50 | + } |
| 51 | + |
| 52 | + int f(string& s) { |
| 53 | + char ch = 'z' + 1; //stroe the smallest char |
| 54 | + int cnt = 0; //stroe the frequency of the smallest char |
| 55 | + for (auto c : s) { |
| 56 | + if (c < ch) { //find the smaller char, reset the count |
| 57 | + cnt = 1; |
| 58 | + ch = c; |
| 59 | + } if (c == ch) { |
| 60 | + cnt++; |
| 61 | + } |
| 62 | + } |
| 63 | + return cnt; |
| 64 | + } |
| 65 | + |
| 66 | + int binary_search(vector<int> &v, int target) { |
| 67 | + int low=0, high=v.size()-1, mid; |
| 68 | + |
| 69 | + while (low < high) { |
| 70 | + mid = low + (high - low) / 2; |
| 71 | + if ( v[mid] > target) { |
| 72 | + high = mid -1; |
| 73 | + } else if (v[mid] <= target) { |
| 74 | + low = mid + 1; |
| 75 | + } |
| 76 | + } |
| 77 | + |
| 78 | + low = v[low] > target ? low : low + 1; |
| 79 | + |
| 80 | + return v.size() - low; |
| 81 | + } |
| 82 | + |
| 83 | +}; |
0 commit comments