D
DevExCode

LeetCode 351: Android Unlock Patterns Solution

Master LeetCode problem 351 (Android Unlock Patterns), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can use backtracking to explore all possible patterns that satisfy the given conditions. We will maintain a visited array to keep track of the keys that have been visited during the traversal. We will also keep a 2D array to represent the valid jumps between keys.

  1. Initialize the 2D array to store the valid jumps between keys. For example, if jump[i][j] is true, it means we can jump from key i to key j.
  2. Start from each key and try to find all valid patterns of length m to n.
  3. For each key, mark it as visited, explore its neighbors that have not been visited yet, and continue the traversal.
  4. Backtrack by unmarking the key as visited to explore other valid patterns.
  5. Count the number of valid patterns found during the traversal.

Time complexity: O(9! * 2^9) as we have 9 choices for the first key and at most 9 steps to explore. Space complexity: O(9) for the visited array and O(9 * 9) for the jump array.

:

Solution Code

class Solution {
    public int numberOfPatterns(int m, int n) {
        int[][] jump = new int[10][10];
        jump[1][3] = jump[3][1] = 2;
        jump[4][6] = jump[6][4] = 5;
        jump[7][9] = jump[9][7] = 8;
        jump[1][7] = jump[7][1] = 4;
        jump[2][8] = jump[8][2] = 5;
        jump[3][9] = jump[9][3] = 6;
        jump[1][9] = jump[9][1] = jump[3][7] = jump[7][3] = 5;

        int[] res = {0};
        boolean[] visited = new boolean[10];
        for (int i = m; i <= n; i++) {
            dfs(1, i - 1, visited, jump, res);
            dfs(2, i - 1, visited, jump, res);
            res[0] *= 4; // Patterns starting from 2, 4, 6, 8 are symmetric
            dfs(5, i - 1, visited, jump, res);
        }
        return res[0];
    }

    private void dfs(int cur, int remain, boolean[] visited, int[][] jump, int[] res) {
        if (remain < 0) return;
        if (remain == 0) {
            res[0]++;
            return;
        }
        visited[cur] = true;
        for (int i = 1; i <= 9; i++) {
            if (!visited[i] && (jump[cur][i] == 0 || visited[jump[cur][i]])) {
                dfs(i, remain - 1, visited, jump, res);
            }
        }
        visited[cur] = false;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 351 (Android Unlock Patterns)?

This page provides optimized solutions for LeetCode problem 351 (Android Unlock Patterns) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 351 (Android Unlock Patterns)?

The time complexity for LeetCode 351 (Android Unlock Patterns) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 351 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 351 in Java, C++, or Python.

Back to LeetCode Solutions