1291. Sequential Digits.md

1291. Sequential Digits

https://leetcode.com/problems/sequential-digits/

An integer has sequential digits if and only if each digit in the number is one more than the previous digit.

Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.

Example 1:

Input: low = 100, high = 300
Output: [123,234]

Example 2:

Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]

Constraints:

• 10 <= low <= high <= 10^9

思路

• 因为 digits 有限，且 digits 一定是从“123456789”中产生，所以可以把长度为low和high之间的所有“递增数”放到一个字典中，再用二分查找找到对应的下标，最终取结果即可

代码

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        
        m = len(str(low))
        n = len(str(high))

        s = "123456789"

        dic = defaultdict(list)
        for digit in range(m, n + 1):
            for i in range(len(s) - digit + 1):
                dic[digit].append(int(s[i:i + digit]))

        start, end = 0, 0
        start = bisect.bisect_left(dic[m], low) 	# 记录在字典中对应最低位的列表的下标
        end = bisect.bisect_right(dic[n], high)		# 记录在字典中对应最高位的列表的下标

        res = []
        if m == n:	# 如果low和high的长度一样，说明结果在一个list中，取下标区间即可
            return dic[m][start:end]

        for digit in range(m, n+1):
            if digit == n:
                res += dic[digit][:end]
            else:
                res += dic[digit][start:]

        return res