Calculate if a move is valid


  • 0
    Y

    Essentially a tree traversal (dfs), but only start from 1, 2 and 5 (since some numbers mirror each other [1,3,7,9] [2,4,6,8] [5], and generate same numbers of patterns).

    The interesting part I wanted to highlight here is the way of determining if we can go to a certain number. We can of course build a "skip" or "bad" array as many suggested, but it can actually be calculated, see function below for details.

    public class Solution {
    
        // leverage the fact that some numbers mirror each other [1,3,7,9] [2,4,6,8] [5]
        public int numberOfPatterns(int m, int n) {
            int res = 0;
            boolean[] visit = new boolean[10];
            
            int[] count = new int[1];
            traverse(1, m, n, 1, count, visit);
            res += 4 * count[0];
            
            count[0] = 0;
            traverse(2, m, n, 1, count, visit);
            res += 4 * count[0];
            
            count[0] = 0;
            traverse(5, m, n, 1, count, visit);
            res += count[0];
            
            return res;
        }
        
        private void traverse(int start, int m, int n, int depth, int[] count, boolean[] visit) {
            if (visit[start]) return;
            visit[start] = true;
            if (depth >= m && depth <= n) count[0]++;
            if (depth < n) {
                for (int i=1; i<=9; i++) {
                    if (i == start) continue;
                    if (!valid(start, i, visit)) continue;
                    traverse(i, m, n, depth+1, count, visit);
                }
            }
            visit[start] = false;
        }
        
        private boolean valid(int a, int b, boolean[] visit) {
            // if either one is 5, always valid
            if (a == 5 || b == 5) return true;
    
            // both odd: crossing sum/2
            if ((a&1) == 1 && (b&1)==1) {
                return visit[(a+b)/2];
            }
    
            // both even, and sum/2 is 5: crossing 5
            if ((a&1) == 0 && (b&1)==0 && (a+b)/2 == 5) {
                return visit[5];
            }
    
            // otherwise, always valid
            return true;
        }
    }
    

Log in to reply
 

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