351. Android Unlock Patterns - cocoder39/coco39_LC GitHub Wiki

351. Android Unlock Patterns

tip: putting visited[i] = true inside dfs() makes the code concise.

time complexity is O(3 * (n - 1)!) = O((n - 1)!) where n the the max length of pattern and n <= 9. space complexity of both skips[][] and visited[] is O(10) = O(1); also we need O(n) space used by the system recursive stack since the max depth of recursion is n

class Solution {
public:
    int numberOfPatterns(int m, int n) {
        vector<vector<int>> skips(10, vector<int>(10));
        //skips[i][j] = k iff line i - j passes througn key k
        skips[1][3] = skips[3][1] = 2;
        skips[1][7] = skips[7][1] = 4;
        skips[3][9] = skips[9][3] = 6;
        skips[7][9] = skips[9][7] = 8;
        skips[1][9] = skips[2][8] = skips[3][7] = skips[4][6] =  
        skips[9][1] = skips[8][2] = skips[7][3] = skips[6][4] = 5;
        vector<bool> visited(10);
        int res = 0;
        
        for (int i = m; i <= n; i++) {
            res += dfs(visited, skips, 1, i - 1) * 4; //1, 3, 7, 9 are symetric
            res += dfs(visited, skips, 2, i - 1) * 4; //2, 4, 6, 8 are symetric
            res += dfs(visited, skips, 5, i - 1);     //5
        }
        return res;
    }
private:
    int dfs(vector<bool>& visited, vector<vector<int>>& skips, int last, int num) {
        visited[last] = true;
        if (num == 0) {
            visited[last] = false;
            return 1;
        }
        
        int res = 0;
        for (int i = 1; i < 10; i++) {
            if (! visited[i]) {
                int skip = skips[last][i];
                if (skip == 0 || visited[skip]) {
                    res += dfs(visited, skips, i, num - 1);
                }
            }
        }
        visited[last] = false;
        return res;
    }
};
⚠️ **GitHub.com Fallback** ⚠️