Skip to content

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<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;
  }
};

 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)