問題
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"].
分析
算法步驟：
- 初始化一個字符串?dāng)?shù)組V赶站，裝入一個空串""幔虏；
- 遍歷Digit string，找到當(dāng)前數(shù)字對應(yīng)的字符數(shù)組S贝椿；
- 遍歷S想括，對當(dāng)前字符s再遍歷V;
- 把V的當(dāng)前字符串v+s存入一個臨時的字符串?dāng)?shù)組T;
- 遍歷結(jié)束后把T復(fù)制給V，開始Digit string的下一輪遍歷烙博。
要點
- 取出一個容器的所有元素瑟蜈，進(jìn)行操作之后再放回容器
- 可以使用指針減少數(shù)據(jù)的拷貝
時間復(fù)雜度
O(3^n)，n是Digit string的長度渣窜。
空間復(fù)雜度
O(3^n)
代碼
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return vector<string>();
static string d2s[] = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
vector<string> v1({""}), v2, *p1 = &v1, *p2 = &v2;
for (int i = 0; i < digits.size(); i++) {
for (int j = 0; j < d2s[digits[i] - '2'].size(); j++) {
for (const string &str : *p1)
p2->push_back(str + d2s[digits[i] - '2'][j]);
}
p1->clear();
swap(p1, p2);
}
return *p1;
}
};
