1170 Compare Strings by Frequency of the Smallest Character 比較字符串最小字母出現(xiàn)頻次
Description:
Let's define a function f(s) over a non-empty string s, which calculates the frequency of the smallest character in s. For example, if s = "dcce" then f(s) = 2 because the smallest character is "c" and its frequency is 2.
Now, given string arrays queries and words, return an integer array answer, where each answer[i] is the number of words such that f(queries[i]) < f(W), where W is a word in words.
Example:
Example 1:
Input: queries = ["cbd"], words = ["zaaaz"]
Output: [1]
Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").
Example 2:
Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
Output: [1,2]
Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").
Constraints:
1 <= queries.length <= 2000
1 <= words.length <= 2000
1 <= queries[i].length, words[i].length <= 10
queries[i][j], words[i][j] are English lowercase letters.
題目描述:
我們來定義一個函數(shù) f(s)叙甸，其中傳入?yún)?shù) s 是一個非空字符串；該函數(shù)的功能是統(tǒng)計 s 中（按字典序比較）最小字母的出現(xiàn)頻次至非。
例如篷朵，若 s = "dcce"勾怒，那么 f(s) = 2婆排，因為最小的字母是 "c"，它出現(xiàn)了 2 次笔链。
現(xiàn)在段只，給你兩個字符串數(shù)組待查表 queries 和詞匯表 words，請你返回一個整數(shù)數(shù)組 answer 作為答案鉴扫，其中每個 answer[i] 是滿足 f(queries[i]) < f(W) 的詞的數(shù)目赞枕，W 是詞匯表 words 中的詞。
示例 :
示例 1：
輸入：queries = ["cbd"], words = ["zaaaz"]
輸出：[1]
解釋：查詢 f("cbd") = 1坪创，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")鹦赎。
示例 2：
輸入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
輸出：[1,2]
解釋：第一個查詢 f("bbb") < f("aaaa")，第二個查詢 f("aaa") 和 f("aaaa") 都 > f("cc")误堡。
提示：
1 <= queries.length <= 2000
1 <= words.length <= 2000
1 <= queries[i].length, words[i].length <= 10
queries[i][j], words[i][j] 都是小寫英文字母
思路:
用一張表記錄 words中的函數(shù)值出現(xiàn)的個數(shù), 函數(shù)的計算方法是對 words中的每個字符串進行排序, 找到最小的字符出現(xiàn)的次數(shù)
之后累計出現(xiàn)的值, 這個值代表大于這個值的個數(shù)有多少
比如 words = ["a","aa","aaa","aaaa"]
count對應的應該是 [0, 1, 1, 1, 1...]表示, 函數(shù)值為1, 2, 3, 4的分別有 1個, 累計值應該是 [0, 4, 3, 2, 1...] 表示大于函數(shù)值 0的有 4個, 大于函數(shù)值 1的有 3個, 以此類推
時間復雜度O(nmlgm), 空間復雜度O(1), n表示 max(words, queries的長度), m表示 max(words, queries中字符串的長度)
代碼:
C++:
class Solution
{
public:
vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words)
{
vector<int> result(queries.size(), 0), count(12, 0);
for (int i = 0; i < words.size(); ++i) ++count[helper(words[i])];
for (int i = 9; i >= 0; --i) count[i] += count[i + 1];
for (int i = 0; i < queries.size(); ++i) result[i] = count[helper(queries[i]) + 1];
return result;
}
private:
int helper(string s)
{
sort(s.begin(), s.end());
int count = 1;
for (int i = 1; i < s.size(); ++i)
{
if (s[i] == s[i - 1]) count++;
else break;
}
return count;
}
};
Java:
class Solution {
public int[] numSmallerByFrequency(String[] queries, String[] words) {
int count[] = new int[12], result[] = new int[queries.length];
for (int i = 0; i < words.length; ++i) ++count[helper(words[i])];
for (int i = 9; i >= 0; --i) count[i] += count[i + 1];
for (int i = 0; i < queries.length; ++i) result[i] = count[helper(queries[i]) + 1];
return result;
}
private int helper(String word) {
char c[] = word.toCharArray();
Arrays.sort(c);
word = new String(c);
int count = 1;
for (int i = 1; i < word.length(); ++i) {
if (word.charAt(i) == word.charAt(i - 1)) count++;
else break;
}
return count;
}
}
Python:
class Solution:
def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
f = lambda x: x.count(min(x))
w = sorted(map(f, words))
return [len(words) - bisect.bisect(w, i) for i in map(f, queries)]
