[Leetcode] 1170. Compare Strings by Frequency of the Smallest Character (Medium)

概述

題目

https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/
f(s) 代表求出一輸入字串中最小字母的數量，求透過都進行 f(s) 操作後，queries 有多少小於 words 的結果

心得

可以觀查到 words 中的排列狀況不影響結果，且若有排列好後再透過 Binary Search 可加速處理過程

Binary Search

思路

Binary Search 問題的變形，故先透過排序預處理後，再 Binary Search 找到結果存回 return array

程式

class Solution(object):
    def numSmallerByFrequency(self, queries, words):
        """
        :type queries: List[str]
        :type words: List[str]
        :rtype: List[int]
        """
        def f(s):
            dic = Counter(s)
            mnv = min(s)
            return dic[mnv]
        
        w = sorted([f(w) for w in words])
        q = [f(q) for q in queries]

        def bs(c):
            def test(m):
                return w[m] <= c

            l, r = 0, len(w)
            while l<r:
                m = (l+r) // 2
                if test(m-1) and not test(m):
                    return m
                if not test(m):
                    r = m
                else:
                    l = m+1
            return l
            
        ret = []
        for c in q:
            ret.append(len(w) - bs(c))
        return ret

使用 bisect

class Solution(object):
    def numSmallerByFrequency(self, queries, words):
        """
        :type queries: List[str]
        :type words: List[str]
        :rtype: List[int]
        """
        def f(s):
            dic = Counter(s)
            mnv = min(s)
            return dic[mnv]
        
        w = sorted([f(w) for w in words])
        q = [f(q) for q in queries]

        ret = []
        for c in q:
            ret.append(len(w) - bisect_right(w, c))
        return ret

Complexity

Time Complexity: O( max(qQ*log(w), wW*log(w)))
本身 words 的排序即是 O( w*log(w) )，每個字串長度最大為 W，時間複雜度為 wW*log(w)，而有 qQ 次操作 (Q 可表 q 個字串的最大長度，共有 q 個字串)，每次 log(w)，故總結果為兩者取大值

PS．1 <= queries[i].length, words[i].length <= 10，題目有說 Q, W <= 10 => 時間複雜度可視為 O(1)

Space Complexity: O(1)
基本上無使用到額外空間

Bucket + Pre-Sum

思路

from hemantdhamija，因為題目求的是 f(s) 之間的大小關係，故若有一方等於，則小於它的也都會成立，即 pre-Sum 概念，故建立 Bucket 系統後透過 pre-Sum，即可更快速的找到 queries 之結果

程式

class Solution(object):
    def numSmallerByFrequency(self, queries, words):
        """
        :type queries: List[str]
        :type words: List[str]
        :rtype: List[int]
        """
        def f(s):
            dic = Counter(s)
            mnv = min(s)
            return dic[mnv]
        
        cnt, ret = [0 for i in range(11)], []

        # words 中最小字母各數，且平移，意在建立 Bucket
        for w in words:
            cnt[f(w)-1] += 1
        
        # PreSum 操作，將數量小於本數的相加
        for freq in range(9, -1, -1):
            cnt[freq] += cnt[freq+1]

        # 取得 queries 的結果
        for q in queries:
            ret.append(cnt[f(q)])
        return ret