我爲leetcode problem 17創建了兩個解決方案，其中它要求您從電話號碼組合中生成所有可能的文本字符串。 "3"結果在["d","e","f"]。兩種算法的大O分析
我的第一個解決方案使用遞歸算法生成字符串和下面給出：
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，但在我看來，空間複雜度會O(n)爲遞歸調用，即其最大深度，O(n)爲緩衝區字符串，O(n*c^n)爲結果字符串。這將總和爲O(n+n*c^n)？
對於時間複雜性，我有點困惑。遞歸的每個級別執行c按下+彈出+遞歸調用乘以下一級的操作次數，因此聽起來像c^1 + c^2 + ... + c^n。另外，長度字符串還有c^n重複。 我如何將它合併爲一個漂亮的大O表示形式？
第二溶液觀看結果作爲混合基數數的數量，並將其轉換成一個字符串作爲可能執行一個int爲十六進制字符串的轉換：
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)爲第一個for循環和另外的O(n*c^n)爲每個可能的結果創建一個結果字符串。最後的大O是O(n+n*c^n)。 我的思維過程是否正確？
編輯：爲了澄清添加到代碼，想象"234"輸入字符串。第一個遞歸解決方案將使用參數(0, "234", lut, r, work)調用generate_strings。 lut是將數字轉換爲相應字符的查找表。 r是包含結果字符串的向量。 work是執行工作的緩衝區。
第一遞歸調用隨後將看到，索引0位數是2與對應，推a到work，然後調用generate_strings與參數(1, "234", lut, r, work)。一旦通話返回，它會將b推至work並沖洗並重復。
當index等於digits的大小時，則生成一個唯一字符串並將該字符串推送到r。
對於第二溶液中，輸入字符串首先被轉換從它的ASCII表示於它的整數表示。例如"234"轉換爲"\x02\x03\x04"。然後，代碼使用這些索引來查找查找表中相應字符的數量，並計算結果中的字符串總數。例如如果輸入的字符串是"234",2對應於abc，它有3個字符。 3對應於def，它有3個字符。 4對應於ghi，它有3個字符。可能的字符串總數爲3*3*3 = 27。
然後代碼使用計數器來表示每個可能的字符串。如果i是15它將通過首先找到15 % 3這是0，與第一個數字的第一個字符（a）相對應進行評估。然後將15除以3即5。 5 % 3是2，它對應於第二個數字的第三個字符，即f。最後用3除5，得到1。 1 % 3是1，它對應於第三個數字的第二個字符h。因此與15對應的字符串是afh。這是針對每個號碼執行的，結果字符串存儲在r中。
你能用英語解釋算法思路嗎？閱讀代碼時可以節省很多頭痛。 – cuongptnk
當你有O時，c^n支配n。你可以簡單地說它是O（c^n）並且是正確的。 –
@cuongptnk當然，我在問題的最後添加了更多細節。 – Alden