मैंने leetcode problem 17 के लिए दो समाधान बनाए हैं जिसमें यह आपको फोन नंबर संयोजन से सभी संभावित टेक्स्ट स्ट्रिंग उत्पन्न करने के लिए कहता है, उदा। "3" परिणाम ["d","e","f"] में परिणाम।बिग-ओ दो एल्गोरिदम का विश्लेषण
मेरा पहला समाधान पुनरावर्ती एल्गोरिदम का उपयोग करता है तार उत्पन्न करने के लिए और नीचे दिया गया है
class Solution {
public:
void fill_LUT(vector<string>& lut) {
lut.clear();
lut.push_back(" ");
lut.push_back("");
lut.push_back("abc");
lut.push_back("def");
lut.push_back("ghi");
lut.push_back("jkl");
lut.push_back("mno");
lut.push_back("pqrs");
lut.push_back("tuv");
lut.push_back("wxyz");
}
void generate_strings(int index, string& digits, vector<string>& lut, vector<string>& r, string& work) {
if(index >= digits.size()) {
r.push_back(work);
return;
}
char idx = digits[index] - '0';
for(char c : lut[idx]) {
work.push_back(c);
generate_strings(index+1, digits, lut, r, work);
work.pop_back();
}
}
vector<string> letterCombinations(string digits) {
vector<string> r;
vector<string> lut;
fill_LUT(lut);
if(digits.size() <= 0)
return r;
string work;
generate_strings(0, digits, lut, r, work);
return r;
}
};
मैं थोड़ा बड़ा-ओ के साथ जंग लगी हूँ, लेकिन मुझे ऐसा लगता है कि अंतरिक्ष जटिलता के लिए O(n) होगा बफर स्ट्रिंग के लिए रिकर्सिव कॉल, यानी इसकी अधिकतम गहराई, O(n), और परिणामी तारों के लिए O(n*c^n)। क्या यह O(n+n*c^n) के साथ मिल जाएगा?
समय जटिलता के लिए मैं थोड़ा उलझन में हूं। रिकर्सन का प्रत्येक स्तर c करता है + पॉप + रिकर्सिव कॉल अगले स्तर तक संचालन की संख्या से गुणा करता है, इसलिए यह c^1 + c^2 + ... + c^n जैसा लगता है। इसके अलावा, लंबाई तारों के c^n डुप्लिकेशंस हैं। मैं इसे एक बड़े बड़े-ओ प्रतिनिधित्व में कैसे समेकित कर सकता हूं?
दूसरा समाधान एक मिश्रित मूलांक संख्या के रूप में परिणामों की संख्या देखता है और एक स्ट्रिंग में बदल देता है के रूप में आप हेक्स स्ट्रिंग रूपांतरण के लिए एक पूर्णांक प्रदर्शन कर सकते हैं: इस मामले में
class Solution {
public:
void fill_LUT(vector<string>& lut) {
lut.clear();
lut.push_back(" ");
lut.push_back("");
lut.push_back("abc");
lut.push_back("def");
lut.push_back("ghi");
lut.push_back("jkl");
lut.push_back("mno");
lut.push_back("pqrs");
lut.push_back("tuv");
lut.push_back("wxyz");
}
vector<string> letterCombinations(string digits) {
vector<string> r;
vector<string> lut;
fill_LUT(lut);
if(digits.size() <= 0)
return r;
unsigned total = 1;
for(int i = 0; i < digits.size(); i++) {
digits[i] = digits[i]-'0';
auto m = lut[digits[i]].size();
if(m > 0) total *= m;
}
for(int i = 0; i < total; i++) {
int current = i;
r.push_back(string());
string& s = r.back();
for(char c : digits) {
int radix = lut[c].size();
if(radix != 0) {
s.push_back(lut[c][current % radix]);
current = current/radix;
}
}
}
return r;
}
};
, मैं मान लें कि अंतरिक्ष जटिलता O(n*c^n) बफर और रिकर्सन के पहले समाधान के समान है, और प्रत्येक जटिल परिणाम के लिए परिणाम स्ट्रिंग बनाने के लिए पहली बार लूप के लिए O(n) और O(n*c^n) होना चाहिए। इसके लिए अंतिम बड़ा-ओ O(n+n*c^n) है। क्या मेरी विचार प्रक्रिया सही है?
संपादित करें: कोड के लिए कुछ स्पष्टीकरण जोड़ने के लिए, "234" का एक इनपुट स्ट्रिंग की कल्पना। पहला रिकर्सिव समाधान पर (0, "234", lut, r, work) तर्कों के साथ कॉल करेगा। lut एक लुकअप टेबल है जो किसी संख्या को इसके संबंधित वर्णों में परिवर्तित करती है। r परिणामस्वरूप स्ट्रिंग वाले वेक्टर हैं। work एक बफर है जहां काम किया जाता है।
पहले पुनरावर्ती कॉल तो देखेंगे कि सूचकांक 0 अंकों 2 जो "abc" के साथ मेल खाती है, work करने के लिए a धक्का, और फिर तर्क (1, "234", lut, r, work) साथ generate_strings कहते हैं। कॉल करने के बाद यह bwork पर धक्का देगा और कुल्ला और दोहराना होगा।
जब indexdigits के आकार के बराबर है तो एक अद्वितीय स्ट्रिंग उत्पन्न की गई है और स्ट्रिंग को r पर धक्का दिया गया है।
दूसरे समाधान के लिए, इनपुट स्ट्रिंग को इसके पूर्णांक प्रतिनिधित्व के पहले एएससीआई प्रतिनिधित्व से पहले परिवर्तित किया जाता है। उदाहरण के लिए "234" को "\x02\x03\x04" में परिवर्तित किया गया है।फिर कोड लुकअप टेबल में संबंधित वर्णों की संख्या देखने के लिए सूचकांक के रूप में उपयोग करता है और परिणामस्वरूप होने वाली तारों की कुल संख्या की गणना करता है। जैसे यदि इनपुट स्ट्रिंग "234" थी, 2abc के साथ मेल खाता है, जिसमें 3 वर्ण हैं। 3def के साथ मेल खाता है जिसमें 3 वर्ण हैं। 4ghi के साथ मेल खाता है जिसमें 3 अक्षर हैं। संभावित तारों की कुल संख्या 3*3*3 = 27 है।
फिर कोड प्रत्येक संभावित तारों का प्रतिनिधित्व करने के लिए काउंटर का उपयोग करता है। यदि i15 थे तो पहले मूल्यांकन किया जाएगा 15 % 3 जो 0 है, जो पहले अंक (a) के पहले वर्ण के अनुरूप है। फिर 153 से विभाजित करें जो 5 है। 5 % 32 है जो दूसरे अंक के लिए तीसरे अक्षर के साथ मेल खाता है, जो f है। अंत में 53 से विभाजित करें और आपको 1 मिलें। 1 % 31 है जो तीसरे अंक के लिए दूसरे वर्ण के साथ मेल खाता है, h। इसलिए 15 के साथ मेल खाने वाली स्ट्रिंग afh है। यह प्रत्येक संख्या के लिए किया जाता है और परिणामी तार r में संग्रहीत होते हैं।
क्या आप अंग्रेजी में अलगो विचारों को समझा सकते हैं? कोड पढ़ने के दौरान यह सिरदर्द का बहुत से बचाता है। – cuongptnk
जब आपके पास ओ, सी^एन हावी है। आप बस यह कह सकते हैं कि यह ओ (सी^एन) है और सही हो। –
@cuongptnk निश्चित रूप से, मैंने अपने प्रश्न के अंत में कुछ और विवरण जोड़ा। – Alden