Java DFS + Concise Conflict Checking


  • 0
    Y
    public class Solution {
        int[] mem1 = new int[10];
        int[] mem2 = new int[10];
        int[] mem5 = new int[10];
        boolean init = false;
        public int numberOfPatterns(int m, int n) {
            if (init == false) {
                init = true;
                initialize();
            }
            int ans = 0;
            for (int i = m; i <= n; i++) ans += 4 * mem1[i] + 4 * mem2[i] + mem5[i];
            return ans;
        }
        
        private void initialize() {
            boolean[] vis;
            vis = new boolean[10];
            vis[1] = true;
            helper(1, 1, vis, mem1);
            vis = new boolean[10];
            vis[2] = true;
            helper(1, 2, vis, mem2);
            vis = new boolean[10];
            vis[5] = true;
            helper(1, 5, vis, mem5);
        }
        
        private void helper(int len, int s, boolean[] vis, int[] mem) {
            if (len > 9) return;
            mem[len] += 1;
            for (int i = 1; i <= 9; i ++) {
                if (vis[i]) continue;
                if (conflict(s, i, vis)) continue;
                vis[i] = true;
                helper(len + 1, i, vis, mem);
                vis[i] = false;
            }
        }
        
        private boolean conflict(int s, int e, boolean[] vis) {
            if (s > e) { int temp = s; s = e; e = temp; }
            int n = s + e;
            if (n == 10 && !vis[5]) return true;
            if (n == 4 && s == 1 && !vis[2]) return true;
            if (n == 8 && s == 1 && !vis[4]) return true;
            if (n == 12 && s == 3 && !vis[6]) return true;
            if (n == 16 && s == 7 && !vis[8]) return true;
            return false;
        }
    }
    

Log in to reply
 

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