[LeetCode] 753. Cracking the Safe 破解密码

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 753. Cracking the Safe 破解密码,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

You can keep inputting the password, the password will automatically be matched against the last n digits entered.html

For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.java

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.node

Example 1:python

Input: n = 1, k = 2
Output: "01"
Note: "10" will be accepted too.

Example 2:c++

Input: n = 2, k = 2
Output: "00110"
Note: "01100", "10011", "11001" will be accepted too. 

Note:git

  1. n will be in the range [1, 4].
  2. k will be in the range [1, 10].
  3. k^n will be at most 4096.

Hint:app

We can think of this problem as the problem of finding an Euler path (a path visiting every edge exactly once) on the following graph: there are $$k^{n-1}$$ nodes with each node having $$k$$ edges. It turns out this graph always has an Eulerian circuit (path starting where it ends.) We should visit each node in "post-order" so as to not get stuck in the graph prematurely.post

连续输入一串密码字符,每次输入一个会按最后一个字符开始匹配。给定密码长度为n,数字个数为k,k的值为0到k-1,用[0, k-1]的数字组成一个密码,使得这个密码必定能打开盒子,返回长度最短的一个密码。ui

思路:若是保证必定能打开箱子,输入的字符串要能覆盖全部的长度为n的字符串。实际上是找到全部由[0, k-1]的数字组成的长度为n的组合,总共有k^n个组合。this

解法:DFS

goal: to find the minimum String that matches all combinations of 1..k with length n.
to build the graph:
node: all possible combinations, e.g. 00, 01, 11, 10;
edge: if the last n - 1 digits of node1 can be transformed to node2 by appending a digit from 1..k, e.g. 01 => (1 + 1) => 11, there will be an edge between node1 and node2 ;
transition:
For each node, we pick its last n - 1 digits. if the digits picked can be transfromed to a valid combination, i.e., another node which has not been visited by appending one more digit from 1..k, we go further following the same pattern... we stop when we have visited all the possible combinations, i.e., all nodes.
start node: 0...0 (n 0's) e.g. 00 for n = 2;
end: when visited.size() == k^n;

Java:

class Solution {
    public String crackSafe(int n, int k) {
        StringBuilder sb = new StringBuilder();
        int total = (int) (Math.pow(k, n));
        for (int i = 0; i < n; i++) sb.append('0');

        Set<String> visited = new HashSet<>();
        visited.add(sb.toString());

        dfs(sb, total, visited, n, k);

        return sb.toString();
    }

    private boolean dfs(StringBuilder sb, int goal, Set<String> visited, int n, int k) {
        if (visited.size() == goal) return true;
        String prev = sb.substring(sb.length() - n + 1, sb.length());
        for (int i = 0; i < k; i++) {
            String next = prev + i;
            if (!visited.contains(next)) {
                visited.add(next);
                sb.append(i);
                if (dfs(sb, goal, visited, n, k)) return true;
                else {
                    visited.remove(next);
                    sb.delete(sb.length() - 1, sb.length());
                }
            }
        }
        return false;
    }

}

Java:

 public String crackSafe(int n, int k) {

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < n; i++) {
            result.append("0");
        }
        Set<String> visited = new HashSet<>();
        visited.add(result.toString());
        crackSafeFrom(result, n, k, (int) Math.pow(k, n), visited);

        return result.toString();
    }

    private boolean crackSafeFrom(StringBuilder result, int n, int k, int total, Set<String> visited) {

        if (visited.size() == total) {
            return true;
        }

        String curNode = result.substring(result.length() - n + 1);

        for (char c = '0'; c < '0' + k; c++) {
            if (!visited.contains(curNode + c)) {
                result.append(c);
                visited.add(curNode + c);
                if (crackSafeFrom(result, n, k, total, visited)) {
                    return true;
                }
                result.deleteCharAt(result.length() - 1);
                visited.remove(curNode + c);
            }
        }
        return false;
    }  

Python:

# Time:  O(n * k^n)
# Space: O(n * k^n)
class Solution(object):
    def crackSafe(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        def dfs(k, node, lookup, result):
            for i in xrange(k):
                neighbor = node + str(i)
                if neighbor not in lookup:
                    lookup.add(neighbor)
                    result.append(str(i))
                    dfs(k, neighbor[1:], lookup, result)
                    break

        result = [str(k-1)]*(n-1)
        lookup = set()
        dfs(k, "".join(result), lookup, result)
        return "".join(result)

Python:  

# Time:  O(n * k^n)
# Space: O(n * k^n)
class Solution(object):
    def crackSafe(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        result = [str(k-1)]*n
        lookup = {"".join(result)}
        total = k**n
        while len(lookup) < total:
            node = result[len(result)-n+1:]
            for i in xrange(k):
                neighbor = "".join(node) + str(i)
                if neighbor not in lookup:
                    lookup.add(neighbor)
                    result.append(str(i))
                    break
        return "".join(result)

Python:  

# Time:  O(k^n)
# Space: O(k^n)
class Solution(object):
    def crackSafe(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        M = k**(n-1)
        P = [q*k+i for i in xrange(k) for q in xrange(M)]  # rotate: i*k^(n-1) + q => q*k + i
        result = [str(k-1)]*(n-1)
        for i in xrange(k**n):
            j = i
            # concatenation in lexicographic order of Lyndon words
            while P[j] >= 0:
                result.append(str(j//M))
                P[j], j = -1, P[j]
        return "".join(result)

C++:  

class Solution {
public:
    string crackSafe(int n, int k) {
        string res = string(n, '0');
        unordered_set<string> visited{{res}};
        helper(n, k, pow(k, n), visited, res);
        return res;
    }
    void helper(int n, int k, int total, unordered_set<string>& visited, string& res) {
        if (visited.size() == total) return;
        string pre = res.substr(res.size() - n + 1, n - 1);
        for (int i = k - 1; i >= 0; --i) {
            string cur = pre + to_string(i);
            if (visited.count(cur)) continue;
            visited.insert(cur);
            res += to_string(i);
            helper(n, k, total, visited, res);
        }
    }
};

C++:  

class Solution {
public:
    string crackSafe(int n, int k) {
        string res = string(n, '0');
        unordered_set<string> visited{{res}};
        for (int i = 0; i < n * k; ++i) {
            string pre = res.substr(res.size() - n + 1, n - 1);
            for (int j = k - 1; j >= 0; --j) {
                string cur = pre + to_string(j);
                if (!visited.count(cur)) {
                    visited.insert(cur);
                    res += to_string(j);
                    break;
                }
            }
        }
        return res;
    }
};

  

  

 

 

All LeetCode Questions List 题目汇总