leetcode problem 17の2つのソリューションが作成されました。電話番号の組み合わせからすべての可能なテキスト文字列を生成するように求められています。 "3"の結果は["d","e","f"]となります。2つのアルゴリズムのBig-O解析
私の最初のソリューションは、文字列を生成するための再帰アルゴリズムを使用し、以下の通りである：私は大きな-Oとビット錆びていますが、宇宙の複雑さがためO(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");
}
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*c^n)となります。この合計はO(n+n*c^n)となりますか？
私はちょっと混乱しています。再帰の各レベルはcプッシュ+ポップ+再帰呼び出しに次のレベルまでの操作数を乗じて実行するので、c^1 + c^2 + ... + c^nのようになります。さらに、n長さの文字列のc^n重複があります。 これをどのようにしてビッグOの表現にまとめることができますか？
第二の溶液を混合基数数として結果の数を見て、あなたは16進文字列への変換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;
}
};
、I空間の複雑さは、最初の解でバッファと再帰を引いたものに似たO(n*c^n)であり、最初のforループではO(n)、可能性のある結果ごとに結果文字列を作成するにはO(n*c^n)が必要です。最終的なビッグオーはO(n+n*c^n)です。 私の思考プロセスは正しいですか？
編集："234"の入力文字列を想像して、コードにいくつかの明確化を追加します。最初の再帰的解は、(0, "234", lut, r, work)という引数でgenerate_stringsを呼び出します。 lutは、数字を対応する文字に変換するルックアップテーブルです。 rは結果の文字列を含むベクトルです。 workは、作業が実行されるバッファです。
最初の再帰呼び出しは、次いで、インデックス0桁がと対応2であることがわかりworkにaを押し、次に引数(1, "234", lut, r, work)でgenerate_stringsを呼び出します。呼び出しが返されるとbをworkにプッシュしてリンスし、繰り返します。
indexがdigitsのサイズと等しい場合、一意の文字列が生成され、文字列がrにプッシュされます。
2番目の解決方法では、入力文字列が最初にASCII表現から整数表現に変換されます。たとえば、"234"は"\x02\x03\x04"に変換されます。次にコードはそれらをインデックスとして使用してルックアップテーブル内の対応する文字の数を検索し、結果に含まれる文字列の総数を計算します。例えば入力文字列が"234"の場合、2はabcに対応し、3文字です。 3はdefに対応し、3文字です。 4は、3文字のghiに対応します。可能な文字列の総数は3*3*3 = 27です。
次に、コードではカウンタを使用して、考えられる各文字列を表します。 iが15である場合、最初に15 % 3であることが評価され、これは0であり、最初の数字の最初の文字（a）に対応します。次に、15を3で割り、これは5です。 5 % 3は2であり、2桁目の3番目の文字に対応します。これはfです。最後に5を3で割り、1になります。 1 % 3は1であり、これは3桁目の2番目の文字であるhに対応します。したがって、数字15に対応する文字列はafhです。これは各番号に対して実行され、結果の文字列はrに格納されます。
英語でalgoのアイデアを説明できますか？それはコードを読むときに頭痛の多くを保存します。 – cuongptnk
Oをお持ちの場合、c^nはnを支配します。あなたは単にそれがO（c^n）だと言って正しいことができます。 –
@cuongptnk確かに、私は私の質問の最後にいくつかの詳細を追加しました。 – Alden