Welcome to Subscribe On Youtube

753. Cracking the Safe

Description

There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1].

The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit.

  • For example, the correct password is "345" and you enter in "012345":
    • After typing 0, the most recent 3 digits is "0", which is incorrect.
    • After typing 1, the most recent 3 digits is "01", which is incorrect.
    • After typing 2, the most recent 3 digits is "012", which is incorrect.
    • After typing 3, the most recent 3 digits is "123", which is incorrect.
    • After typing 4, the most recent 3 digits is "234", which is incorrect.
    • After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks.

Return any string of minimum length that will unlock the safe at some point of entering it.

 

Example 1:

Input: n = 1, k = 2
Output: "10"
Explanation: The password is a single digit, so enter each digit. "01" would also unlock the safe.

Example 2:

Input: n = 2, k = 2
Output: "01100"
Explanation: For each possible password:
- "00" is typed in starting from the 4th digit.
- "01" is typed in starting from the 1st digit.
- "10" is typed in starting from the 3rd digit.
- "11" is typed in starting from the 2nd digit.
Thus "01100" will unlock the safe. "01100", "10011", and "11001" would also unlock the safe.

 

Constraints:

  • 1 <= n <= 4
  • 1 <= k <= 10
  • 1 <= kn <= 4096

Solutions

  • class Solution {
        private Set<Integer> vis = new HashSet<>();
        private StringBuilder ans = new StringBuilder();
        private int mod;
    
        public String crackSafe(int n, int k) {
            mod = (int) Math.pow(10, n - 1);
            dfs(0, k);
            ans.append("0".repeat(n - 1));
            return ans.toString();
        }
    
        private void dfs(int u, int k) {
            for (int x = 0; x < k; ++x) {
                int e = u * 10 + x;
                if (vis.add(e)) {
                    int v = e % mod;
                    dfs(v, k);
                    ans.append(x);
                }
            }
        }
    }
    
  • class Solution {
    public:
        string crackSafe(int n, int k) {
            unordered_set<int> vis;
            int mod = pow(10, n - 1);
            string ans;
            function<void(int)> dfs = [&](int u) {
                for (int x = 0; x < k; ++x) {
                    int e = u * 10 + x;
                    if (!vis.count(e)) {
                        vis.insert(e);
                        dfs(e % mod);
                        ans += (x + '0');
                    }
                }
            };
            dfs(0);
            ans += string(n - 1, '0');
            return ans;
        }
    };
    
  • class Solution:
        def crackSafe(self, n: int, k: int) -> str:
            def dfs(u):
                for x in range(k):
                    e = u * 10 + x
                    if e not in vis:
                        vis.add(e)
                        v = e % mod
                        dfs(v)
                        ans.append(str(x))
    
            mod = 10 ** (n - 1)
            vis = set()
            ans = []
            dfs(0)
            ans.append("0" * (n - 1))
            return "".join(ans)
    
    
  • func crackSafe(n int, k int) string {
    	mod := int(math.Pow(10, float64(n-1)))
    	vis := map[int]bool{}
    	ans := &strings.Builder{}
    	var dfs func(int)
    	dfs = func(u int) {
    		for x := 0; x < k; x++ {
    			e := u*10 + x
    			if !vis[e] {
    				vis[e] = true
    				v := e % mod
    				dfs(v)
    				ans.WriteByte(byte('0' + x))
    			}
    		}
    	}
    	dfs(0)
    	ans.WriteString(strings.Repeat("0", n-1))
    	return ans.String()
    }
    

All Problems

All Solutions