मान लीजिए हमारे पास एक बॉक्स है जो पासवर्ड से सुरक्षित है। पासवर्ड n अंकों का एक क्रम है जहां प्रत्येक अंक पहले k अंकों 0, 1, ..., k-1 में से एक हो सकता है। तो, जब हम पासवर्ड डालते हैं, तो दर्ज किए गए अंतिम n अंक स्वचालित रूप से सही पासवर्ड के विरुद्ध मिलान किए जाएंगे।
तो उदाहरण के लिए, मान लीजिए सही पासवर्ड "563" है, यदि हम "285639" डालते हैं, तो बॉक्स खुल जाएगा क्योंकि सही पासवर्ड दर्ज किए गए पासवर्ड के सफिक्स (suffix) से मेल खाता है। हमें किसी भी पासवर्ड की न्यूनतम लंबाई ज्ञात करनी है जो किसी बिंदु पर इसे दर्ज करने पर बॉक्स को खोलने की गारंटी देता है।
जब इनपुट n = 2 और k = 2 जैसा है, तो परिणाम "01100", "00110", "10011", "11001" हो सकता है, उनमें से कोई भी एक।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -
- एक सेट visited परिभाषित करें
- एक फंक्शन dfs() परिभाषित करें, यह s, k लेगा,
- i := 0 से प्रारंभ करें, जब i < k, i बढ़ाते हुए, करें -
- temp := s को i के स्ट्रिंग के साथ जोड़ें
- यदि temp visited में नहीं है, तो -
- temp को visited में डालें
- temp := temp का सबस्ट्रिंग इंडेक्स 1 से अंत तक प्राप्त करें
- dfs(temp, k)
- ret := ret को i के स्ट्रिंग के साथ जोड़ें
- मुख्य विधि से, निम्न करें -
- यदि n, 1 के समान है और k, 1 के समान है, तो -
- "0" वापस करें
- ret := खाली स्ट्रिंग, s := खाली स्ट्रिंग
- i := 0 से प्रारंभ करें, जब i < n - 1, i बढ़ाते हुए, करें -
- s := s को "0" के साथ जोड़ें
- dfs(s, k)
- i := 0 से प्रारंभ करें, जब i < n - 1, i बढ़ाते हुए, करें -
- ret := ret को "0" के साथ जोड़ें
- ret वापस करें
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
उदाहरण
#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)); }इनपुट
2 2
आउटपुट
01100