Android Unlock Patterns — LeetCode 351 Python Solution
MediumLeetCode PremiumBit ManipulationDynamic ProgrammingBacktrackingBitmask
- Problem
- #351
- Pattern
- Backtracking
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- m = 1, n = 1
- Output
- 9
Python solution
Python
class Solution:
def numberOfPatterns(self, m: int, n: int) -> int:
def dfs(i: int, cnt: int = 1) -> int:
if cnt > n:
return 0
vis[i] = True
ans = int(cnt >= m)
for j in range(1, 10):
x = cross[i][j]
if not vis[j] and (x == 0 or vis[x]):
ans += dfs(j, cnt + 1)
vis[i] = False
return ans
cross = [[0] * 10 for _ in range(10)]
cross[1][3] = cross[3][1] = 2
cross[1][7] = cross[7][1] = 4
cross[1][9] = cross[9][1] = 5
cross[2][8] = cross[8][2] = 5
cross[3][7] = cross[7][3] = 5
cross[3][9] = cross[9][3] = 6
cross[4][6] = cross[6][4] = 5
cross[7][9] = cross[9][7] = 8
vis = [False] * 10
return dfs(1) * 4 + dfs(2) * 4 + dfs(5)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n·m) (typical) |
| Space | O(n·m) or optimized auxiliary |
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 351. Android Unlock Patterns is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 351. Android Unlock Patterns?
- LeetCode 351. Android Unlock Patterns is rated Medium on LeetCode.
- What topics does LeetCode 351. Android Unlock Patterns cover?
- LeetCode 351. Android Unlock Patterns is tagged Bit Manipulation, Dynamic Programming, Backtracking and Bitmask on LeetCode.
- Is LeetCode 351. Android Unlock Patterns a premium problem?
- Yes. LeetCode 351. Android Unlock Patterns is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.