_351. Android Unlock Patterns.md

351. Android Unlock Patterns

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : August 13, 2024

Last updated : August 13, 2024

---

Related Topics : Dynamic Programming, Backtracking, Bit Manipulation, Bitmask

Acceptance Rate : 53.06 %

---

Solutions

• m351.py

Python

m351.py

class Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        self.cases = [(1, 9), (3, 7),
                      (1, 3), (4, 6), (7, 9),
                      (1, 7), (2, 8), (9, 3),]

        def dfs(prev: List[int], nxt: Set[int], minn: int, maxx: int) -> int :
            output = 0
            if minn <= len(prev) <= maxx :
                output += 1
            if not nxt or len(prev) >= maxx :
                return output


            temp = nxt.copy()
            for i in temp :
                if prev and ((prev[-1], i) in self.cases or (i, prev[-1]) in self.cases):
                    if (prev[-1] + i) // 2 not in prev :
                        continue

                nxt.remove(i)
                prev.append(i)
                output += dfs(prev, nxt, m, n)
                nxt.add(prev.pop())

            return output

        return dfs([], set([1,2,3,4,5,6,7,8,9]), m, n)