351. Android Unlock Patterns

• Time: $O(n!)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public: int numberOfPatterns(int m, int n) { int ans = 0; vector> across(10, vector(10)); vector 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& seen, const vector>& 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 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)