# Android Unlock Patterns

### 描述​

Android devices have a special lock screen with a 3 x 3 grid of dots. Users can set an "unlock pattern" by connecting the dots in a specific sequence, forming a series of joined line segments where each segment's endpoints are two consecutive dots in the sequence. A sequence of k dots is a valid unlock pattern if both of the following are true:

• All the dots in the sequence are distinct.
• If the line segment connecting two consecutive dots in the sequence passes through any other dot, the other dot must have previously appeared in the sequence. No jumps through non-selected dots are allowed.

Here are some example valid and invalid unlock patterns:

• The 1st pattern [4,1,3,6] is invalid because the line connecting dots 1 and 3 pass through dot 2, but dot 2 did not previously appear in the sequence.
• The 2nd pattern [4,1,9,2] is invalid because the line connecting dots 1 and 9 pass through dot 5, but dot 5 did not previously appear in the sequence.
• The 3rd pattern [2,4,1,3,6] is valid because it follows the conditions. The line connecting dots 1 and 3 meets the condition because dot 2 previously appeared in the sequence.
• The 4th pattern [6,5,4,1,9,2] is valid because it follows the conditions. The line connecting dots 1 and 9 meets the condition because dot 5 previously appeared in the sequence.

Given two integers m and n, return the number of unique and valid unlock patterns of the Android grid lock screen that consist of at least m keys and at most n keys.

Two unlock patterns are considered unique if there is a dot in one sequence that is not in the other, or the order of the dots is different.

Example 1:

Input: m = 1, n = 1
Output: 9

Example 2:

Input: m = 1, n = 2
Output: 65

Constraints:

• 1 <= m, n <= 9

### 代码​

// Android Unlock Patterns// Time Complexity O(n!), Space Complexity: O(n)public class Solution {    public int numberOfPatterns(int m, int n) {        int[][] jumps = build_jump_table();        boolean[] visited = new boolean[10];        int count = 0;        for(int i = m; i <= n; ++i) {            count += dfs(visited, jumps, 1, i - 1) * 4;  // 1, 3, 7, 9 are symmetric            count += dfs(visited, jumps, 2, i - 1) * 4;  // 2, 4, 6, 8 are symmetric            count += dfs(visited, jumps, 5, i - 1);      // 5        }        return count;    }    private static int dfs(boolean visited[], int[][] jumps, int num, int remain) {        if(remain == 0) return 1;        int count = 0;        visited[num] = true;        for(int i = 1; i <= 9; ++i) {            int mid = jumps[num][i]; // Edge num->i jumps over mid            if(!visited[i] && (mid == 0 || (visited[mid]))) {                count += dfs(visited, jumps, i, remain - 1);            }        }        visited[num] = false;        return count;    }    private int[][] build_jump_table() {        int[][] jumps = new int[10][10]; // jump table, 0 means adjacent        jumps[1][3] = jumps[3][1] = 2; // The edge 1->3 jumps over 2        jumps[1][7] = jumps[7][1] = 4;        jumps[3][9] = jumps[9][3] = 6;        jumps[7][9] = jumps[9][7] = 8;        jumps[2][8] = jumps[8][2] = jumps[4][6] = jumps[6][4] = 5;        jumps[1][9] = jumps[9][1] = jumps[3][7] = jumps[7][3] = 5;        return jumps;    }}