Problem
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 02
and 043
are not allowed.
Example 1:
Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.
Example 2:
Input: n = 2, k = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
Constraints:
2 <= n <= 9
0 <= k <= 9
Solution
/**
* @param {number} n
* @param {number} k
* @return {number[]}
*/
var numsSameConsecDiff = function(n, k) {
var res = [];
for (var i = 1; i < 10; i++) {
helper([i], n - 1, k, res);
}
return res;
};
var helper = function(arr, n, k, res) {
if (n === 0) {
res.push(+arr.join(''));
return;
}
if (n < 0 || n > 9) {
return;
}
var last = arr[arr.length - 1];
if (last - k >= 0) {
arr.push(last - k);
helper(arr, n - 1, k, res);
arr.pop();
}
if (k !== 0 && last + k < 10) {
arr.push(last + k);
helper(arr, n - 1, k, res);
arr.pop();
}
};
Explain:
Start with 1 ~ 9, dfs (top down) to get all answers.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).