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!

  • 0
    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.


Log in to reply
 

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