问题
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"].
分析
算法步骤：
- 初始化一个字符串数组V，装入一个空串""；
- 遍历Digit string，找到当前数字对应的字符数组S；
- 遍历S，对当前字符s再遍历V;
- 把V的当前字符串v+s存入一个临时的字符串数组T;
- 遍历结束后把T复制给V，开始Digit string的下一轮遍历。
要点
- 取出一个容器的所有元素，进行操作之后再放回容器
- 可以使用指针减少数据的拷贝
时间复杂度
O(3^n)，n是Digit string的长度。
空间复杂度
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;
}
};
