Leetcode - Compare Strings by Frequency of the Smallest Character

violet posted @ Apr 07, 2020 08:56:07 AM in 算法 with tags Algorithm array count sort , 324 阅读

https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/

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 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").

Very straightforward.

func numSmallerByFrequency(queries []string, words []string) []int {
    result := make([]int, len(queries))
    wordFs := make([]int, len(words))
    for i := 0; i < len(words); i++ {
        wordFs[i] = f(words[i])
    }
    for i := 0; i < len(queries); i++ {
        queryF := f(queries[i])
        tmp := 0
        for j := 0; j < len(words); j++ {
            if queryF < wordFs[j] {
                tmp++
            }
        }
        result[i] = tmp
    }
    return result
}

func f(word string) int {
    count := make([]int, 26)
    for i := 0; i < len(word); i++ {
        count[word[i]-'a']++
    }
    for i := 0; i < 26; i++ {
        if count[i] != 0 {
            return count[i]
        }
    }
    return 0
}