前往
大廳
主題

LeetCode - 1170. Compare Strings by Frequency of the Smallest Character 解題心得

Not In My Back Yard | 2024-03-25 12:00:12 | 巴幣 0 | 人氣 39

題目連結:


題目意譯:
令函數 f(s) 為一個字串 s 中最小字典序的字元之出現次數。例如說,如果 s = "dcce",則 f(s) = 2,因為其中字典序最小為 'c',而其出現次數為 2。

你被給定一個字串陣列 words,以及另一個字串詢問陣列 queries。對於每一筆詢問 queries[i],請統計 words 中有多少字詞滿足 f(queries[i]) < f(W),對於 words 中每一個字詞 W。

回傳一個整數陣列 answer,其中 answer[i] 是第 i 筆詢問的答案。

限制:
1 ≦ queries.length ≦ 2000
1 ≦ words.length ≦ 2000
1 ≦ queries[i].length, words[i].length ≦ 10
queries[i][j] 、 words[i][j] 由小寫英文字母組成。



範例測資:
範例 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")。


解題思維:
先把 words 中每一個字詞 W 的 f(W) 之值算出來。然後將這些數值排序(小到大或大到小皆可)。

然後對於每一筆詢問 queries[i],求出其 f(queries[i]) 之值之後便可以利用二分搜尋法(Binary Search)來在上面排序後的數值來得到有多少 f(W) 大於 f(queries) 之值。而此即為 answer[i] 之值。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作