LeetCode Solutions
351. Android Unlock Patterns
Time: $O(n!)$ Space: $O(n)$
class Solution {
public:
int numberOfPatterns(int m, int n) {
int ans = 0;
vector<vector<int>> across(10, vector<int>(10));
vector<bool> seen(10);
across[1][3] = across[3][1] = 2;
across[1][7] = across[7][1] = 4;
across[3][9] = across[9][3] = 6;
across[7][9] = across[9][7] = 8;
across[1][9] = across[9][1] = across[2][8] = across[8][2] = across[3][7] =
across[7][3] = across[4][6] = across[6][4] = 5;
ans += dfs(m, n, 1, 1, seen, across) * 4; // 1, 3, 7, 9 are symmetric
ans += dfs(m, n, 2, 1, seen, across) * 4; // 2, 4, 6, 8 are symmetric
ans += dfs(m, n, 5, 1, seen, across); // 5
return ans;
}
private:
int dfs(int m, int n, int u, int depth, vector<bool>& seen,
const vector<vector<int>>& across) {
if (depth > n)
return 0;
seen[u] = true;
int ans = depth >= m ? 1 : 0;
for (int v = 1; v <= 9; ++v) {
if (v == u || seen[v])
continue;
const int acrossed = across[u][v];
if (acrossed == 0 || seen[acrossed])
ans += dfs(m, n, v, depth + 1, seen, across);
}
seen[u] = false;
return ans;
}
};
class Solution {
public int numberOfPatterns(int m, int n) {
int ans = 0;
int[][] across = new int[10][10];
boolean[] seen = new boolean[10];
across[1][3] = across[3][1] = 2;
across[1][7] = across[7][1] = 4;
across[3][9] = across[9][3] = 6;
across[7][9] = across[9][7] = 8;
across[1][9] = across[9][1] = across[2][8] = across[8][2] = across[3][7] = across[7][3] =
across[4][6] = across[6][4] = 5;
ans += dfs(m, n, 1, 1, seen, across) * 4; // 1, 3, 7, 9 are symmetric
ans += dfs(m, n, 2, 1, seen, across) * 4; // 2, 4, 6, 8 are symmetric
ans += dfs(m, n, 5, 1, seen, across); // 5
return ans;
}
private int dfs(int m, int n, int u, int level, boolean[] seen, int[][] across) {
if (level > n)
return 0;
seen[u] = true;
int ans = level >= m;
for (int v = 1; v <= 9; ++v) {
if (v == u || seen[v])
continue;
final int acrossed = across[u][v];
if (acrossed == 0 || seen[acrossed])
ans += dfs(m, n, v, level + 1, seen, across);
}
seen[u] = false;
return ans;
}
}
class Solution:
def numberOfPatterns(self, m: int, n: int) -> int:
seen = set()
accross = [[0] * 10 for _ in range(10)]
accross[1][3] = accross[3][1] = 2
accross[1][7] = accross[7][1] = 4
accross[3][9] = accross[9][3] = 6
accross[7][9] = accross[9][7] = 8
accross[1][9] = accross[9][1] = accross[2][8] = accross[8][2] = \
accross[3][7] = accross[7][3] = accross[4][6] = accross[6][4] = 5
def dfs(u: int, depth: int) -> int:
if depth > n:
return 0
seen.add(u)
ans = 1 if depth >= m else 0
for v in range(1, 10):
if v == u or v in seen:
continue
accrossed = accross[u][v]
if not accrossed or accrossed in seen:
ans += dfs(v, depth + 1)
seen.remove(u)
return ans
# 1, 3, 7, 9 are symmetric
# 2, 4, 6, 8 are symmetric
return dfs(1, 1) * 4 + dfs(2, 1) * 4 + dfs(5, 1)