Re: [閒聊] 每日leetcode

[Meaverzt (單推凜寶)]

題目：

給定一個有很多字串的array

要找出有多少字串有跟題目給的pref一樣的prefix

思路一：

直接暴力解

遍歷每個字串看前綴是不是pref

Code:

def prefixCount(words,pref):
    num=0
    words[ i for i in words if len(pref)<=len(i)]
    while num!=len(pref):
        words=[i for i in words if i[num]==pref[num]]
        num+=1
    return len(words)

時間複雜度 O(n*m)

n:words的長度 m:pref的長度

思路二

如果直接把words拿去sort

前綴一樣的會排在一起

假設前綴是abc

只要去二分搜第一個abc出現的位置

跟如果有一個abd要插入應該要放的位置

兩個相減就是答案了

Code:

def prefixCount(words, pref):
    def search(arr, target):
        left, right = 0, len(arr)
        while left < right:
            mid = left + (right - left) // 2
            if arr[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

    words.sort()
    next = pref[:-1] + chr(ord(pref[-1]) + 1)
    start = search(words, pref)
    end = search(words, next)
    return end - start

不知道這樣sort時間複雜度要怎麼算捏

說不定還比第一個慢

肥肥就這樣了
--
https://i.imgur.com/5XtXJd3.jpeg


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.237.35.22 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1736433037.A.D9D.html
推 oin1104: 可能要看m有沒有比logn大 應該有 所以也許比較快 嗎
→ oin1104: 大師
推 sustainer123: nlogn