LeetCode Letter Combinations of a Phone Numberクラシックコンビネーション問題
2494 ワード
Letter Combinations of a Phone Number
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Note: Although the above answer is in lexicographical order, your answer could be in any order you want.
この問題は主にアルファベットを取り出す方法と他のアルファベット列の組み合わせを知っています.
3つのループが含まれています.
第1サイクル:すべての「アルファベット列」(2,3で表されるabc,defを指す)を取り出し、1つずつ組み合わせます.
2つ目のループ:以前に組み合わせられた「すべての結果の組合せ」(Output:[「ad」、「ae」...)を指す)新しい文字列と組み合わせる
3つ目のループ:新しく取り出した「アルファベット列」と結果を組み合わせたアルファベット列を組み合わせる
注意:
1起動組み合わせのアルファベット列は「」である.空の文字列、しかも文字列の組み合わせがない場合も結果は空です
2第3のサイクルの組み合わせの新しいアルファベット列は+元の結果の後にあり、最後の組み合わせの新しいアルファベット列を特殊に処理する必要があるほか、組み合わせた新しいアルファベット列は元の組み合わせのアルファベット列に代わる必要がある.
この方法はよく覚えてこそ、プログラムを書くことができると思います.
//2014-1-25 update
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note: Although the above answer is in lexicographical order, your answer could be in any order you want.
この問題は主にアルファベットを取り出す方法と他のアルファベット列の組み合わせを知っています.
3つのループが含まれています.
第1サイクル:すべての「アルファベット列」(2,3で表されるabc,defを指す)を取り出し、1つずつ組み合わせます.
2つ目のループ:以前に組み合わせられた「すべての結果の組合せ」(Output:[「ad」、「ae」...)を指す)新しい文字列と組み合わせる
3つ目のループ:新しく取り出した「アルファベット列」と結果を組み合わせたアルファベット列を組み合わせる
注意:
1起動組み合わせのアルファベット列は「」である.空の文字列、しかも文字列の組み合わせがない場合も結果は空です
2第3のサイクルの組み合わせの新しいアルファベット列は+元の結果の後にあり、最後の組み合わせの新しいアルファベット列を特殊に処理する必要があるほか、組み合わせた新しいアルファベット列は元の組み合わせのアルファベット列に代わる必要がある.
この方法はよく覚えてこそ、プログラムを書くことができると思います.
class Solution {
public:
vector<string> letterCombinations(string digits)
{
vector<string> vst;
// 1: “”; ,
vst.push_back("");
string str[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
for (int i = 0; i < digits.length(); i++)
{
for (int j = vst.size()-1; j >=0 ; j--)
{
int k = int(digits[i] - '2');
for (int r = 0; r < str[k].length(); r++)
{// 2: +
if (r == str[k].length()-1)
{
vst[j] += str[k][r];
}
// , 。
else vst.push_back(vst[j]+str[k][r]);
}
}
}
return vst;
}
};
//2014-1-25 update
vector<string> letterCombinations(string digits)
{
vector<string> rs;
rs.push_back("");
string str[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
for (int d = 0; d < digits.size(); d++)
{
int i = digits[d]-'2';
for (int j = rs.size() - 1; j >= 0 ; j--)
{
for (int k = str[i].size()-1; k >= 0 ; k--)
{
if (k == 0) rs[j] += str[i][k];
else rs.push_back(rs[j]+str[i][k]);
}
}
}
return rs;
}