[Leetcode] 744. Find Smallest Letter Greater Than Target (Easy)

概述

題目

https://leetcode.com/problems/find-smallest-letter-greater-than-target/
給定一依序排列好的字母組，求最小大等於 target 的字母

心得

有排序就有高機率是 Binary Search，哪怕此題 Easy BF 也能解

BF

思路

暴搜一次看有沒有符合題意的字母，若無則回傳首位

程式

class Solution(object):
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        l, t = letters, target
        n = len(l)
        for i in range(n):
            if t < l[i]:
                return l[i]
        return l[0]

Complexity

Time Complexity: O(n)
全部走過一次

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

Binary Search

思路

經典的 Binary Search，只不過要注意可以多個數同時相等，故求的是最端點的

程式

class Solution(object):
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        n = len(letters)
        l, r = 0, n

        def test(m):
            return letters[m] <= target

        while l<r:
            m = (l+r) // 2
            if test(m-1) and not test(m):
                return letters[m]
            if not test(m):
                r = m
            else:
                l = m+1
        return letters[l%len(letters)]

一行解，同理但使用 bisect 函式

程式

class Solution(object):
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        return letters[bisect_right(letters, target) % len(letters)]

Complexity

Time Complexity: O(log n)
操作 log n 次

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

O(1)

思路

from jiny2021 ，因為英文字母只有 26 個小寫，故 traverse 一次後就知道所求

程式

class Solution(object):
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        ast = set(letters)
        alp = "abcdefghijklmnopqrstuvwxyz"
        for l in alp[alp.index(target)+1:]:
            if l in ast:
                return l
        return letters[0]