Breadth-First Search
Backtracking
Description
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:
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def numsSameConsecDiff ( self , n : int , k : int ) -> List [ int ]:
ans = []
def dfs ( n , k , t ):
if n == 0 :
ans . append ( t )
return
last = t % 10
if last + k <= 9 :
dfs ( n - 1 , k , t * 10 + last + k )
if last - k >= 0 and k != 0 :
dfs ( n - 1 , k , t * 10 + last - k )
for i in range ( 1 , 10 ):
dfs ( n - 1 , k , i )
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 class Solution {
public int [] numsSameConsecDiff ( int n , int k ) {
List < Integer > res = new ArrayList <> ();
for ( int i = 1 ; i < 10 ; ++ i ) {
dfs ( n - 1 , k , i , res );
}
int [] ans = new int [ res . size () ] ;
for ( int i = 0 ; i < res . size (); ++ i ) {
ans [ i ] = res . get ( i );
}
return ans ;
}
private void dfs ( int n , int k , int t , List < Integer > res ) {
if ( n == 0 ) {
res . add ( t );
return ;
}
int last = t % 10 ;
if ( last + k <= 9 ) {
dfs ( n - 1 , k , t * 10 + last + k , res );
}
if ( last - k >= 0 && k != 0 ) {
dfs ( n - 1 , k , t * 10 + last - k , res );
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public :
vector < int > ans ;
vector < int > numsSameConsecDiff ( int n , int k ) {
for ( int i = 1 ; i < 10 ; ++ i )
dfs ( n - 1 , k , i );
return ans ;
}
void dfs ( int n , int k , int t ) {
if ( n == 0 ) {
ans . push_back ( t );
return ;
}
int last = t % 10 ;
if ( last + k <= 9 ) dfs ( n - 1 , k , t * 10 + last + k );
if ( last - k >= 0 && k != 0 ) dfs ( n - 1 , k , t * 10 + last - k );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 func numsSameConsecDiff ( n int , k int ) [] int {
var ans [] int
var dfs func ( n , k , t int )
dfs = func ( n , k , t int ) {
if n == 0 {
ans = append ( ans , t )
return
}
last := t % 10
if last + k <= 9 {
dfs ( n - 1 , k , t * 10 + last + k )
}
if last - k >= 0 && k != 0 {
dfs ( n - 1 , k , t * 10 + last - k )
}
}
for i := 1 ; i < 10 ; i ++ {
dfs ( n - 1 , k , i )
}
return ans
}
GitHub