My clean Java solution, very easy to understand


  • 0
    H
    public int numberOfPatterns(int m, int n) {
        boolean[][] board = new boolean[3][3];
        int result = 0;
        
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                board[i][j] = true;
                result += helper(board, i, j, m, n, 1);
                board[i][j] = false;
            }
        }
        
        return result;
    }
    
    private int helper(boolean[][] board, int i, int j, int m, int n, int count) {
        if (count > n) return 0;
        
        int result = (count >= m) ? 1 : 0;
        
        for (int x = 0; x < 3; x++) {
            for (int y = 0; y < 3; y++) {
                if (board[x][y] ||
                    (x == i && Math.abs(y - j) == 2 && !board[x][1]) ||
                    (y == j && Math.abs(x - i) == 2 && !board[1][y]) ||
                    (Math.abs(x - i) == 2 && Math.abs(y - j) == 2 && !board[1][1])) {
                    continue;
                }
                
                board[x][y] = true;
                result += helper(board, x, y, m, n, count + 1);
                board[x][y] = false;
            }
        }
        
        return result;
    }

  • 0
    I

    I implemented your code in python, but I got TLE, not sure wat is going on lol, do you see any differences? I don't

    class Solution(object):
        def dfs(self, m, n, row, col, visited, patternLen):
            if patternLen > n:
                return 0
                
            patterns = 0
            visited[i][j] = True
            if m <= patternLen <= n:
                patterns = 1
                
            for i in xrange(3):
                for j in xrange(3):
                    if ((visited[i][j]) or 
                       (i == row and abs(j - col) == 2 and not visited[i][1]) or 
                       (j == col and abs(i - row) == 2 and not visited[j][1]) or 
                       (abs(i - row) == 2 and abs(j - col) == 2 and not visited[1][1])):
                           continue
                    
                    patterns += self.dfs(m, n, i, j, visited, patternLen + 1)
                    
            visited[i][j] = False
            return patterns
                    
        
        def numberOfPatterns(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            visited = [[False for i in xrange(3)] for j in xrange(3)]
            patterns = 0
            for i in xrange(3):
                for j in xrange(3):
                    patterns += self.dfs(m, n, i, j, visited, 1)
                        
            return patterns

Log in to reply
 

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