Bẻ khóa két sắt trong C ++

Giả sử chúng ta có một hộp được bảo vệ bằng mật khẩu. Mật khẩu là một dãy gồm n chữ số trong đó mỗi chữ số có thể là một trong k chữ số đầu tiên 0, 1, ..., k-1. Vì vậy, khi chúng tôi đặt mật khẩu, n chữ số cuối cùng được nhập sẽ tự động được khớp với mật khẩu chính xác.

Vì vậy, ví dụ, giả sử mật khẩu chính xác là "563", nếu chúng ta đặt "285639", hộp sẽ mở ra vì mật khẩu chính xác khớp với hậu tố của mật khẩu đã nhập. Chúng tôi phải tìm bất kỳ mật khẩu nào có độ dài tối thiểu được đảm bảo để mở hộp tại một số thời điểm khi nhập.

Khi đầu vào giống như n =2 và k =2, thì kết quả có thể là “01100”, “00110”, “10011”, “11001”, bất kỳ một trong số chúng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một tập hợp được gọi là đã ghé thăm
• Xác định một hàm dfs (), hàm này sẽ nhận s, k,
• để khởi tạo i:=0, khi i
• temp:=s nối i dưới dạng chuỗi
• nếu tạm thời không được truy cập, thì -
  • chèn tạm thời vào đã truy cập
  • temp:=lấy chuỗi con của nhiệt độ từ chỉ mục 1 đến cuối
  • dfs (tạm thời, k)
  • ret:=ret nối i dưới dạng chuỗi

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   set <string> visited;
   string ret;
   string crackSafe(int n, int k) {
      if(n == 1 && k == 1) return "0";
      ret = "";
      string s = "";
      for(int i = 0; i < n - 1; i++){
         s += "0";
      }
      dfs(s, k);
      for(int i = 0; i < n - 1; i++) ret += "0";
      return ret;
   }
   void dfs(string s, int k) {
      string temp;
      for(int i = 0; i < k; i++){
         temp = s + to_string(i);
         if(!visited.count(temp)){
            visited.insert(temp);
            temp = temp.substr(1);
            dfs(temp, k);
            ret += to_string(i);
         }
      }
   }
};
main(){
   Solution ob;
   cout << (ob.crackSafe(2,2));
}

Đầu vào

2
2

Đầu ra

01100