note0351.md

Leetcode 351. Android Unlock Patterns

• Type: Search dfs(top-down/bottom-up)
• Approach:
  • The tricky part of the issue is that we can build a dictionary to prestore the pairs, like (n1, n3): n2, which means that n1 and n3 can cross n2 in key lock screen. By this, when we get a new number, just check whether the pair (current number, new number) is in the dictionary and if so, check whether the corresponding cross number is in our visisted set.
  1. Top-down:
     • Use a set to store visited number in case of duplicated number and a path to store the current path.
     • The base case is when the length of the path is between m and n, result is added 1; if length of the path is larger than n, return
     • Don't forget to remove new number after backtracking.
  2. Bottom-up:
     • The tricky part is that we don't need to start from each number but just 1, 2, 5 because others are duplicated counting.
     • We store visited number, current number and remaining steps which means the remaining keys we can use.
     • The base case is when remaining step is equal to 0, return 1; when it is less than 0, return 0.
• Complexity:
  • Time: O(n)
  • Space: O(n)