Java easy understand DFS solution (72ms)


  • 6
    Q

    If we use the symmetry, we can only start from 1, 2 and 5 then multiply the results of 1 and 2 by 4. (170ms) Thanks to @woaizuguo999

    int res=0;
    public int numberOfPatterns(int m, int n) {
        boolean[][] keyboard = new boolean[3][3];
        int ret=0;
        for (int p=m;p<=n;p++){
            for (int i=0;i<2;i++){
                for (int j=0;j<2;j++){
                    if (j == 0 && i == 1) continue;
                    keyboard[i][j] = true;
                    helper(keyboard,p-1,i,j);
                    keyboard[i][j] = false;
                    ret += (i == 1 && j == 1)? res:4*res;
                    res=0;
                }
            }
        }
        return ret;
    }
    private void helper(boolean[][] keyboard,int left, int x, int y){
        if (left == 0){
            res++;
            return;
        }
        for (int i=0;i<3;i++){
            for (int j=0;j<3;j++){
                if (keyboard[i][j] 
                    ||  (x==i && Math.abs(y-j)>1) && !keyboard[x][1]
                    ||  (y==j && Math.abs(x-i)>1) && !keyboard[1][y]
                    ||  (x+y == i+j) && Math.abs(x-i) >1 && !keyboard[1][1]
                    ||  (x-y == i-j) && Math.abs(x-i) >1 && !keyboard[1][1]
                    ||  (x == i && y == j)) {
                    continue;
                }
                else{
                    keyboard[i][j] = true;
                    helper(keyboard,left-1,i,j);
                    keyboard[i][j] = false;
                }
            }
        }
    }
    

    And we can continue improving the performance by using symmetry in step 1, which is the next step after start. For start from 1, only consider 2 6 and 5. For start from 2, only consider 3,6,9 and 5. For start from 5, only consider 1 and 2.(72 ms)

    int res=0;
    public int numberOfPatterns(int m, int n) {
        boolean[][] keyboard = new boolean[3][3];
        int ret=0;
        for (int p=m;p<=n;p++){
            for (int i=0;i<2;i++){
                for (int j=0;j<2;j++){
                    if (j == 0 && i == 1) continue;
                    keyboard[i][j] = true;
                    helper(keyboard,p-1,i,j,true);
                    keyboard[i][j] = false;
                    ret += (i == 1 && j == 1)? res:4*res;
                    res=0;
                }
            }
        }
        return ret;
    }
    
    private void dfshelper(boolean[][] keyboard, int left, int x, int y){
        keyboard[x][y] = true;
        helper(keyboard,left,x,y,false);
        keyboard[x][y] = false;
    }
    
    private void helper(boolean[][] keyboard,int left, int x, int y, boolean step1){
        if (left == 0){
            res++;
            return;
        }
        if (step1){
            if (x == 0 && y == 0){
                dfshelper(keyboard,left-1,0,1);
                dfshelper(keyboard,left-1,1,2);
                int temp = 2*res;
                res = 0;
                dfshelper(keyboard,left-1,1,1);
                res += temp;
            }
            if (x == 0 && y == 1){
                dfshelper(keyboard,left-1,0,2);
                dfshelper(keyboard,left-1,1,2);
                dfshelper(keyboard,left-1,2,2);
                int temp = 2*res;
                res = 0;
                dfshelper(keyboard,left-1,1,1);
                res += temp;
            }
            if (x == 1 && y == 1){
                dfshelper(keyboard,left-1,0,0);
                dfshelper(keyboard,left-1,0,1);
                res=res*4;
            }
        }
        else{
            for (int i=0;i<3;i++){
                for (int j=0;j<3;j++){
                    if (keyboard[i][j] 
                        ||  (x==i && Math.abs(y-j)>1) && !keyboard[x][1]
                        ||  (y==j && Math.abs(x-i)>1) && !keyboard[1][y]
                        ||  (x+y == i+j) && Math.abs(x-i) >1 && !keyboard[1][1]
                        ||  (x-y == i-j) && Math.abs(x-i) >1 && !keyboard[1][1]
                        ||  (x == i && y == j)) {
                        continue;
                    }
                    else{
                        keyboard[i][j] = true;
                        helper(keyboard,left-1,i,j,false);
                        keyboard[i][j] = false;
                    }
                }
            }
        }
    }
    

  • 0
    H

    Does this solution consider movement from (0, 0) to (2, 1) etc.?


  • 0
    Q

    Yes. In the rule 3, it seems that if we jump from 1 to 8, we don't pass keys. We have a path between 4 and 5.


  • 0
    H

    oh, i see. i thought 4 and 5 have to be visited previously...


  • 0
    W
    1. The code initializing keyboard is not needed. By default, the elements in keyboard will be false.

    2. Don't need to start from all 3x3 elements. 1,3,7,9 are similar, only need to process one of them and then the result x 4. Also same case for 2,4,6,8. (i.e. only need to start from 1,2,5)


  • 0
    Q

    Thank you for pointing out. It will save a lot of time by utilizing the symmetry in the start step and step 1. For the initialization, I want to show the initial status is all false. It seems useless.


  • 3
    A

    I rewrote the code to make it a little simpler and easier to understand. The fastest runtime is 155ms.

    int res = 0;
    
    public int numberOfPatterns(int m, int n) {
        int ret = 0;
        int[][] start = {{0, 0}, {0, 1}, {1, 1}};
        boolean[][] board = new boolean[3][3];
        for (int len = m; len <= n; len++) {
            for (int i = 0; i < 3; i++) {
                int x = start[i][0], y = start[i][1];
                dfs(x, y, len, board);
                ret += i != 2 ? res * 4 : res;
                res = 0;
            }
        }
        return ret;
    }
    
    private void dfs(int x, int y, int len, boolean[][] board) {
        if (len == 1) { res++; return; }
        board[x][y] = true;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j]
                    || (i == x && Math.abs(j - y) > 1 && !board[x][1])
                    || (j == y && Math.abs(i - x) > 1 && !board[1][y])
                    || ((i + j == x + y || i - x == j - y) && Math.abs(i - x) > 1 && !board[1][1])) {
                    continue;
                }
                dfs(i, j, len - 1, board);
            }
        }
        board[x][y] = false;
    }

  • 1
    Y

    What's the time complexity of this solution?


Log in to reply
 

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