Simple and concise Java solution in 69ms


  • 33
    D

    The general idea is DFS all the possible combinations from 1 to 9 and skip invalid moves along the way.

    We can check invalid moves by using a jumping table. e.g. If a move requires a jump and the key that it is crossing is not visited, then the move is invalid. Furthermore, we can utilize symmetry to reduce runtime, in this case it reduced from ~120ms to ~70ms.

    I felt clueless when first encountered this problem, and considered there must be lots of edge cases. Turns out, it's pretty straight forward. Hope this solution helps :D

    private int[][] jumps;
    private boolean[] visited;
    
    public int numberOfPatterns(int m, int n) {
        jumps = new int[10][10];
        jumps[1][3] = jumps[3][1] = 2;
        jumps[4][6] = jumps[6][4] = 5;
        jumps[7][9] = jumps[9][7] = 8;
        jumps[1][7] = jumps[7][1] = 4;
        jumps[2][8] = jumps[8][2] = 5;
        jumps[3][9] = jumps[9][3] = 6;
    	jumps[1][9] = jumps[9][1] = jumps[3][7] = jumps[7][3] = 5;
        visited = new boolean[10];
        int count = 0;
    	count += DFS(1, 1, 0, m, n) * 4; // 1, 3, 7, 9 are symmetrical
    	count += DFS(2, 1, 0, m, n) * 4; // 2, 4, 6, 8 are symmetrical
    	count += DFS(5, 1, 0, m, n);
    	return count;
    }
    
    private int DFS(int num, int len, int count, int m, int n) {
    	if (len >= m) count++; // only count if moves are larger than m
    	len++;
    	if (len > n) return count;
        visited[num] = true;
        for (int next = 1; next <= 9; next++) {
            int jump = jumps[num][next];
            if (!visited[next] && (jump == 0 || visited[jump])) {
                count = DFS(next, len, count, m, n);
            }
        }
    	visited[num] = false; // backtracking
        return count;
    }

  • 0
    D
    This post is deleted!

  • 0
    D
    This post is deleted!

  • 1
    J

    good solution! I modified a little.
    public class Solution {

    int[][] pattern;
    boolean[] used;

    public int numberOfPatterns(int m, int n) {
        if(m<=0||n>9||m>n) return 0;
        //if(n==1) return 9;
        int sum=0;
       
        pattern = new int[10][10];
    
        for(int i=1;i<5;i++){
            pattern[5-i][i+5] = 5;
            pattern[5+i][5-i] = 5;
        }
        for(int i=2;i<9;i=i+6){
            pattern[i-1][i+1] = i;
            pattern[i+1][i-1] = i;
        }
        for(int i=4;i<7;i=i+2){
            pattern[i-3][i+3] = i;
            pattern[i+3][i-3] = i;
        }
        int count = 1;
        used = new boolean[10];
        used[0] = true;
        
        sum += dfs(1,count,m,n)*4;
        sum += dfs(2,count,m,n)*4;
        sum += dfs(5,count,m,n);
        return sum;
    }
    public int dfs(int k,int count,int m, int n){
        int sum = 0;
        if(count>=m){
            sum++;
        }
        if(count>=n){
            return sum;
        }
        
        used[k] = true;
        count++;
    
        for(int i=1;i<10;i++){
                
            if( !used[i] && used[pattern[k][i]])
                sum = sum + dfs(i,count,m,n);
                
        }
        used[k] = false;
        return sum;
        
    }
    

    }


  • 0
    W

    Very concise and elegant.


  • 2
    A

    Can you explain in the DFS
    if (len >= m) count++;

    why do we need to increase count when len>=m??

    Also, in the for loop of DFS, isn't it like:

    count+= DFS(````` ) ?
    should there be a + ?


  • 0
    D

    Because only moves larger than m are valid moves. The question requires us only count moves between m and n;


  • 0
    T

    beautiful solution! I like it


  • 0
    B

    @david-liu May you explain the idea behind the jump array a little more?


  • 0
    L

    @david-liu Is a move from 1 to 6 a valid move? Since jumps[1][6] is initialized to 0 it will be during the dfs routine, but I don't understand why it should.


  • 0
    Q

    @leetcodewinner I had the same question. After checking Android lock pad, I find 1-6 could be linked directly.


  • 0

    Similar but may be a little easier to remember without the optimization:

    public class Solution {
        
        private static final int[][] ON_PATH = buildOnPath();
        
        public int numberOfPatterns(int m, int n) {
            boolean visited[] = new boolean[10];
            visited[0] = true;
            return numberOfPatterns(visited, m, n, 0, 0, 0);
        }
        
        private int numberOfPatterns(boolean[] visited, int m, int n, int prev, int curr, int length) {
            if (length != 0 && (visited[curr] || length > n)) return 0; // path is too long or we already used this key
            if (!visited[ON_PATH[prev][curr]]) return 0; // we haven't visited the key that was on the way here
            
            visited[curr] = true;
            
            int result = 0;
            for (int i = 1; i < 10; i++)
                result += numberOfPatterns(visited, m, n, curr, i, length + 1);
                
            visited[curr] = false; // backtrack
            
            return length >= m ? result + 1 : result; // if current path is valid length then include it in result
        }
        
        private static int[][] buildOnPath() {
            int onPath[][] = new int[10][10];
            
            onPath[1][3] = onPath[3][1] = 2;
            onPath[1][7] = onPath[7][1] = 4;
            onPath[3][9] = onPath[9][3] = 6;
            onPath[7][9] = onPath[9][7] = 8;
            
            onPath[1][9] = onPath[9][1] =
            onPath[2][8] = onPath[8][2] =
            onPath[3][7] = onPath[7][3] =
            onPath[4][6] = onPath[6][4] = 5;
            
            return onPath;
        }
    }
    

  • 1
    S

    Very clever solution! The top voted answer runs from scratch for each length, but this one just reuses results from shorter paths.


  • 0

    @antonioybw said in Simple and concise Java solution in 69ms:

    count+= DFS(````` ) ?
    should there be a + ?

    Same question. Anybody can explain?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.