Java DFS solution with clear explanations and optimization, beats 97.61% (12ms)


  • 196
    Z

    The optimization idea is that 1,3,7,9 are symmetric, 2,4,6,8 are also symmetric. Hence we only calculate one among each group and multiply by 4.

    public class Solution {
        // cur: the current position
        // remain: the steps remaining
        int DFS(boolean vis[], int[][] skip, int cur, int remain) {
            if(remain < 0) return 0;
            if(remain == 0) return 1;
            vis[cur] = true;
            int rst = 0;
            for(int i = 1; i <= 9; ++i) {
                // If vis[i] is not visited and (two numbers are adjacent or skip number is already visited)
                if(!vis[i] && (skip[cur][i] == 0 || (vis[skip[cur][i]]))) {
                    rst += DFS(vis, skip, i, remain - 1);
                }
            }
            vis[cur] = false;
            return rst;
        }
        
        public int numberOfPatterns(int m, int n) {
            // Skip array represents number to skip between two pairs
            int skip[][] = new int[10][10];
            skip[1][3] = skip[3][1] = 2;
            skip[1][7] = skip[7][1] = 4;
            skip[3][9] = skip[9][3] = 6;
            skip[7][9] = skip[9][7] = 8;
            skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;
            boolean vis[] = new boolean[10];
            int rst = 0;
            // DFS search each length from m to n
            for(int i = m; i <= n; ++i) {
                rst += DFS(vis, skip, 1, i - 1) * 4;    // 1, 3, 7, 9 are symmetric
                rst += DFS(vis, skip, 2, i - 1) * 4;    // 2, 4, 6, 8 are symmetric
                rst += DFS(vis, skip, 5, i - 1);        // 5
            }
            return rst;
        }
    }

  • 1
    V

    It's the most elegant and laconic solution for the problem I have seen. Thank you.


  • 2
    L

    I like your skip array, it is concise!


  • 0
    Y

    What's the time complexity of this solution?


  • 0

    This solution is awesome :)


  • 0
    X
    This post is deleted!

  • 0

    niubi.......


  • 0
    W

    Awesome solution... Really helped me wrap my head around it typing it out myself. Here it is in JS

    var DFS = function(visited, skip, current, remaining) {
        if (remaining < 0) return 0;
        if (remaining === 0) return 1;
        visited[current] = true;
        let result = 0;
        for (let i = 1; i <= 9; i++) {
            if (!visited[i] && (skip[current][i] === 0 || (visited[skip[current][i]]))) {
                result += DFS(visited, skip, i, remaining-1);
            }
        }
        visited[current] = false;
        return result;
    }
    
    /**
     * @param {number} m
     * @param {number} n
     * @return {number}
     */
    var numberOfPatterns = function(m, n) {
        let skip = Array.from(new Array(10), x=>new Array(10).fill(0));
    
        skip[1][3] = skip[3][1] = 2;
        skip[1][7] = skip[7][1] = 4;
        skip[3][9] = skip[9][3] = 6;
        skip[7][9] = skip[9][7] = 8;
        skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;
        
        let visited = new Array(10).fill(false);
        let result = 0;
        
        for (let i = m; i <= n; i++) {
            result += DFS(visited, skip, 1, i-1) * 4;
            result += DFS(visited, skip, 2, i-1) * 4;
            result += DFS(visited, skip, 5, i-1);
        }
        
        return result;
    };
    

    Thanks for sharing :)


  • 2
    H

    Thanks for sharing the solution. This is awesome. Here are the implementation in python.

    class Solution(object):
        def numberOfPatterns(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            skip = [[0 for j in range(10)] for i in range(10)]
            skip[1][3] = skip[3][1] = 2
            skip[1][7] = skip[7][1] = 4
            skip[3][9] = skip[9][3] = 6
            skip[7][9] = skip[9][7] = 8
            skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5
            vis = [False for i in range(10)]
            rst = 0
            for i in range(m, n+1):
                rst += self.dfs(vis, skip, 1, i-1) * 4
                rst += self.dfs(vis, skip, 2, i-1) * 4
                rst += self.dfs(vis, skip, 5, i-1) 
            return rst
                
        def dfs(self, vis, skip, cur, remain):
            if remain < 0: return 0
            if remain == 0: return 1
            vis[cur] = True
            rst = 0
            for i in range(1,10):
                if not vis[i] and (skip[cur][i] == 0 or vis[skip[cur][i]]):
                    rst += self.dfs(vis, skip, i, remain-1)
            vis[cur] = False
            return rst
    

  • 0
    Q

    @yinan7 Isn't it 3* 81 * (m-n)?


  • 2
    Z

    @yinan7 I think the time complexity is
    O(3 * sigma(i = m to n) ((8!) / (9 - i)!)), but not very precise.

    Starting from 5, we have 8 choices. After we choose one number as our next step, suppose 3, we have 7 choices remaining. Then we have 6 remaining, we keep this procedure until we reach step i. The search tree is of size (8!) / (9 - i)!

    Search tree starting from 1 or 2 apperantly will not have as much node as starting from 5, but the difference is of constant factor.


  • 1
    M

    Really brilliant idea. Just one comment: if(remain < 0) return 0; is not necessary since remain will never be negative. I removed that line and got accepted. Thanks for sharing this solution.


  • 4
    H

    How about, skip[2][9], skip[9][2], why they are zero by default ?
    Are they applicable in

    if(!vis[i] && (skip[cur][i] == 0 || (vis[skip[cur][i]]))) {
                rst += DFS(vis, skip, i, remain - 1);
    }
    

  • 0
    J

    @hangbo Nope. Actually there is no node between 2 and 9, and thus skip[2][9] = 0 (refer to this link: http://weibo.com/3848372087/Dsbg57f8G?type=comment#_rnd1476730279026)


  • 1
    G

    anyone can tell me why if(remain < 0) return 0; this statement is meaning? we could directly return 1 when remain == 0, so remain would not be less than 0


  • 1
    N

    Excellent solution.
    What will be the time complexity fro this solution?


  • 1
    D

    @zzz1322 good solution. But your base case could just be
    if (remain == 0) {
    return 1;
    }


  • 0
    L

    Very clear! Thanks.


  • 0
    M

    @zzz1322 Regarding this part of code // DFS search each length from m to n, can't we use DP to build longer lengths from shorter ones, rather than calling it again and again? Please excuse me if it is a dumb question.


  • 3
    R

    How is this solution returning correct result?

    For example, it gives following paths starting from 7 length 2 : 72, 74,75,76,78. 74,75 and 78 are acceptable but how do we have 72 and 76 are in the result?


Log in to reply
 

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