Java solution using backtracking with one loop


  • 0
    S

    A modification of the solution: https://discuss.leetcode.com/topic/58892/java-solution-using-backtracking-with-one-loop/1

    We can use backtracking to automatically include all patterns whose length is within [m,n]

    public class Solution {
        public int numberOfPatterns(int m, int n) {
            int[][] jump = new int[10][10];
            jump[1][3] = jump[3][1] = 2;
            jump[1][7] = jump[7][1] = 4;
            jump[3][9] = jump[9][3] = 6;
            jump[7][9] = jump[9][7] = 8;
            jump[1][9] = jump[9][1] = jump[3][7] = jump[7][3] = jump[2][8] = jump[8][2] = jump[4][6] = jump[6][4] = 5;
            
            boolean[] isVisited = new boolean[10];
    
            int total = dfs(1, isVisited, jump, m, n, 0)*4 + dfs(2, isVisited, jump, m, n, 0)*4 + dfs(5, isVisited, jump, m, n, 0);
            
            return total;
            
        }
        
        //return the number of valid patterns starting from 'start'
        public int dfs(int start, boolean[] isVisited, int[][] jump, int m, int n, int currLength) {
            currLength += 1;
            if (currLength > n) {
                return 0;
            }
            
            isVisited[start]  = true;
            int sum = 0;
            if (currLength <= n && currLength >= m) sum += 1;
            
            for (int i = 1; i <= 9; i++) {
                if (!isVisited[i] && (jump[start][i] == 0 || isVisited[jump[start][i]])) {
                    sum += dfs(i, isVisited, jump, m, n, currLength);
                }
            }
            
            isVisited[start] = false;
            return sum;
        }
    }
    

Log in to reply
 

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