My accepted clean Java solution.


  • 0
    Z
    public class Solution {
        public int numberOfPatterns(int m, int n) {
            int[][] A = new int[10][10];
            A[1][3] = 2;
            A[1][7] = 4;
            A[1][9] = 5;
            A[2][8] = 5;
            A[3][1] = 2;
            A[3][7] = 5;
            A[3][9] = 6;
            A[4][6] = 5;
            A[6][4] = 5;
            A[7][1] = 4;
            A[7][3] = 5;
            A[7][9] = 8;
            A[8][2] = 5;
            A[9][1] = 5;
            A[9][3] = 6;
            A[9][7] = 8;
            boolean[] map = new boolean[10];
            int[] res = new int[1];
            for(int i = 1;i <= 9;i++) {
                backtrace(A,map,i,0,m,n,res);
            }
            return res[0];
        }
        
        public void backtrace(int[][] A, boolean[] map, int i,int len, int m, int n, int[] res) {
            if(len >= n) return;
            map[i] = true;
            if(len + 1 >= m ) res[0]++;
            for(int j = 1;j<=9;j++) {
                if(map[j] || (A[i][j]!=0 && !map[A[i][j]] ) ) continue;
                backtrace(A,map,j,len+1,m,n,res);
            }
            map[i] = false;
        }
    }

Log in to reply
 

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