Cracking the Safe LeetCode solution in Java

1
class Solution {
2
  String ans;
3

4
  public String crackSafe(int n, int k) {
5
    int minLen = (int) Math.pow(k, n) + (n - 1);
6

7
    dfs("", n, k, new HashSet<String>(), minLen);
8
    return ans;
9
  }
10

11
  private void dfs(String s, int n, int k, HashSet<String> visited, int minLen) {
12
    if (s.length() == minLen) {
13
      ans = s;
14
      return;
15
    }
16
    if (s.length() > minLen) {
17
      return;
18
    }
19

20
    for (int i = 0; i < k; i++) {
21
      s += String.valueOf(i);
22
      String lastN = s.substring(Math.max(0, s.length() - n), s.length());
23
      // If already in hashset, rollback and continue;
24
      if (visited.contains(lastN)) {
25
        s = s.substring(0, s.length() - 1);
26
        continue;
27
      }
28
      if (lastN.length() == n) { // only put n length string in hashset
29
        visited.add(lastN);
30
      }
31

32
      dfs(s, n, k, visited, minLen);
33
      if (visited.size() == minLen - n + 1) {
34
        return;
35
      } // if hashset contains all possible combinations just return
36
      visited.remove(lastN);
37
      s = s.substring(0, s.length() - 1);
38
    }
39
  }
40
}