Problem statement

https://leetcode.com/problems/single-row-keyboard/

Solution

We can use bfs approach here: add numbers [0, 1, ..., 9] to queue and each time we extract number num from the left, we add at most two possible candidates to the right. In this way we can be sure that numbers are sorted. If we have number between low and high, we add it to answer. Also, if we have num > high, we can stop.

Complexity

Time complexity is O(9*2^(k-1)), where k is maximum number of digits, space complexity as well.

Code

class Solution:
    def countSteppingNumbers(self, low, high):
        queue = deque(range(10))
        ans = []
        
        while queue:
            num = queue.popleft()
            if low <= num <= high: ans += [num]
            if num > high: return ans
            last_digit = num % 10
            if num == 0: continue
            for new in [last_digit - 1, last_digit + 1]:
                if 0 <= new <= 9:
                    queue.append(num*10 + new)