算法
时间复杂度: O(2^n)
空间复杂度: O(2^n)
C++代码
class Solution {
public:
static vector<string> letterCombinations(const string &digits) {
if (digits.empty()) {
return {};
}
vector<string> res(1, "");
for (const auto digit : digits) {
vector<string> res1(res.size() << 2);
int r1 = 0;
for (const auto &str : res) {
for (const auto ch : digitsArr[digit - '2']) {
res1[r1] = str;
res1[r1].push_back(ch);
++r1;
}
}
res1.resize(r1);
res = move(res1);
}
return res;
}
private:
static const array<string, 8> digitsArr;
};
const array<string, 8> Solution::digitsArr = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
Java代码
class Solution {
public static List<String> letterCombinations(final String digits) {
if (digits.isEmpty()) {
return new ArrayList<>();
}
List<String> res = new ArrayList<>(1);
res.add("");
for (int i = 0; i < digits.length(); ++i) {
final char digit = digits.charAt(i);
final List<String> res1 = new ArrayList<>(res.size() << 2);
for (String str : res) {
final String strDigit = digitsArr[digit - '2'];
for (int j = 0; j < strDigit.length(); ++j) {
final char ch = strDigit.charAt(j);
res1.add(str + ch);
}
}
res = res1;
}
return res;
}
private static String[] digitsArr = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
}
Python3代码
class Solution:
__digitArr = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
def letterCombinations(self, digits: str) -> list:
if not digits:
return []
res = [""]
for digit in digits:
res1 = []
for str in res:
for ch in Solution.__digitArr[ord(digit) - ord('2')]:
res1.append(str + ch)
res = res1
return res