Algorithm: Leetcode Contest 405

3211. Generate Binary Strings Without Adjacent Zeros

Solution

class Solution {
    public List<String> validStrings(int n) {
        // dfs
        List<String> res = new ArrayList<>();
        
        dfs(new StringBuilder(), 0, -1, n, res);
        
        return res;
        
    }
    
    private void dfs(StringBuilder cur, int i, int last, int n, List<String> res) {
        if (i == n) {
            res.add(new String(cur));
            return;
        }
        
        // add 1
        dfs(cur.append(1), i + 1, 1, n, res);
        cur.setLength(cur.length() - 1);
        
        if (last != 0) {
            dfs(cur.append(0), i + 1, 0, n, res);
            cur.setLength(cur.length() - 1);
        }
    
    }
}

3212. Count Submatrices With Equal Frequency of X and Y

Solution

class Solution {
    public int numberOfSubmatrices(char[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        boolean [][] hasX = new boolean[grid.length][grid[0].length];
        
        // fill first cell
        dp[0][0] = getInc(grid[0][0]);
        hasX[0][0] = seenX(grid[0][0]);
        
        // fill first row
        for(int col = 1; col < grid[0].length; col++) {
            hasX[0][col] = hasX[0][col - 1] || seenX(grid[0][col]);
            dp[0][col] = dp[0][col - 1] + getInc(grid[0][col]);
        }
        
        // fill first col
        for(int row = 1; row < grid.length; row++) {
            hasX[row][0] = hasX[row - 1][0] || seenX(grid[row][0]);
            dp[row][0] = dp[row - 1][0] + getInc(grid[row][0]);
        }
        
        // fill normal cell
        for(int row = 1; row < grid.length; row++) {
            for(int col = 1; col < grid[0].length; col++) {
                hasX[row][col] = hasX[row - 1][col] || hasX[row][col - 1] || seenX(grid[row][col]);
                dp[row][col] = dp[row - 1][col] + dp[row][col - 1] - dp[row - 1][col - 1] + getInc(grid[row][col]);
            }
        }
        
        // count valid cell, hasX = true, dp = 0
        int res = 0;
        for(int row = 0; row < grid.length; row++) {
            for(int col = 0; col < grid[0].length; col++) {
                if(hasX[row][col] && dp[row][col] == 0) {
                    res++;
                }
            }
        }
        
        return res;
    }
    
    private int getInc(char c) {
        if (c == 'X') {
            return 1;
        } else if (c == 'Y') {
            return -1;
        } else {
            return 0;
        }
    }
    
    private boolean seenX(char c) {
        return c == 'X';
    }
}