LeetCode Numbers With Same Consecutive Differences Solution
Given two integers n and k, return an array of all the integers of length
n where the difference between every two consecutive digits is
k. You may return the answer in any order.
Note that the integers should not have leading zeros. Integers as
043 are not allowed.
n = 3, k = 7
Explanation: Note that
070 is not a valid number, because it has leading zeroes.
n = 2, k = 1
2 <= n <= 9
0 <= k <= 9
Problem Link: https://leetcode.com/problems/numbers-with-same-consecutive-differences/
We want to build up the numbers from the leftmost digit to the rightmost.
n is >= 2 and there should not be leading zeros, we will start from one digit (1-9) and call our backtracking helper to construct the next digits.
num in the implementation) will store an integer instead of a list to save space and time.
We want to apply backtracking1 template. We fill in the logic:
start_index == n, when the constucted number contains
get_edges: the next digit can be
cur_digit +- k
cur_digit + k <= 9and
cur_digit - k >= 0to avoid the next digit being out of bound. Note that in the implementation, if
cur_digit+k == cur_digit - k, we must avoid the duplicate by checking whether
1def numsSameConsecDiff(self, n: int, k: int) -> List[int]: 2 def dfs(start_index, num): 3 if start_index == n: # num is n digits, add to ans 4 ans.append(num) 5 return 6 cur_digit = num % 10 # current digit 7 if (cur_digit - k >= 0): 8 dfs(start_index + 1, num * 10 + (cur_digit - k)) 9 if (cur_digit + k <= 9 and k != 0): # avoid duplicate when k = 0 10 dfs(start_index + 1, num * 10 + (cur_digit + k)) 11 ans =  12 for i in range(1, 10): # first digit can be 1-9 13 dfs(1, i) 14 return ans