[LeetCode351] Android Unlock Pat

Solution

转载 https://medium.com/@rebeccahezhang/leetcode-351-android-unlock-patterns-d9bae4a8a958

We sum all the valid patterns when using m keys, m+1keys, … n keys together to get the result.

In each case, we use DFS to count the number of valid paths from the current number (1–9)to the remaining numbers. To optimize, calling DFS less than 9 times, we can use the symmetry of the 3 by 3 matrix. If we start from 1 or 3 or 7 or 9, the valid paths number should be the same. If we start from 2 or 4 or 6 or 8, the valid paths number are also the same. Start from 5 is the third case. So the total is :

return value of DFS (start from 1) * 4 +
return value of DFS (start from 2) * 4 + 
return value of DFS (start from 5)

One of the invalid case can be: I want to create a pattern using 1 and 3. First you touch 1, moving your finger to the right to reach 3 — oh no, there is 2 in the middle that we don’t want it in my password! Here are all the invalid patterns:

start key | end key | unselected number on the path
1 | 3 | 2
3 | 1 | 2
1 | 7 | 4
7 | 1 | 4
3 | 9 | 6
9 | 3 | 6
7 | 9 | 8
9 | 7 | 8
1 | 9 | 5
9 | 1 | 5
2 | 8 | 5
8 | 2 | 5
3 | 7 | 5
7 | 3 | 5
4 | 6 | 5
6 | 4 | 5

We need to create a matrix to keep a record of unselected numbers on the path between two keys.

class Solution {
    public int numberOfPatterns(int m, int n) {
        // skip: the number you cannot cross through unless it has been visited
        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[3][7] = skip[7][3] = 5;
        skip[2][8] = skip[8][2] = skip[4][6] = skip[6][4] = 5;
        
        int result = 0;
        boolean[] visited = new boolean[10];
        
        for (int i = m; i <= n; i++) {
            result += numberOfPatternsHelper (1, visited, skip, i - 1) * 4; // start Number, visited matrix, skip matrix, remaining key number
            result += numberOfPatternsHelper (2, visited, skip, i - 1) * 4; 
            result += numberOfPatternsHelper (5, visited, skip, i - 1); 
        }
        
        return result;
    }
    
    //remainKeyCount: how many keys remaining is needed in this pattern
    public int numberOfPatternsHelper (int currentNumber, boolean[] visited, int[][] skip, int remainKeyCount) {
        if (remainKeyCount == 0) {
            return 1;
        }
        
        int result = 0;
        visited [currentNumber] = true;
        
        for (int i = 1; i <= 9; i++) {
            int crossThroughNumber = skip[currentNumber][i];
            
            // valid movement: next number hasn't visited, and crossThroughNumber is valid (adjacent) or has been visited
            if (!visited[i] && (crossThroughNumber == 0 || visited [crossThroughNumber])) {
                result += numberOfPatternsHelper (i, visited, skip, remainKeyCount - 1);
            }
        }
        visited [currentNumber] = false;
        
        return result;
    }
}

Now in DFS, we keep trying to find the next valid key. What is a valid candidate? We need to make sure if the next key hasn’t been visited, and either it’s adjacent to the current key, or it’s the key in between (recorded as the unselected number on the path)but has been visited.