Last Updated: 2023-12-25 07:47:28 Monday
-- TOC --
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
输入一个数字字符串，仅包含[2-9]，输出所有可能的数字代表的字母组合，任意顺序。数字到字母的mapping，与手机上的输入法一样，如下：
2: abc
3: def
4: ghi
5: jkl
6: mno
7: pqrs
8: tuv
9: wxyz
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints:
题目并没有说明输入的字符串中，是否会存在重复的数字，是可以重复的。
class Solution:
digit2letter = {'2':('a','b','c'),
'3':('d','e','f'),
'4':('g','h','i'),
'5':('j','k','l'),
'6':('m','n','o'),
'7':('p','q','r','s'),
'8':('t','u','v'),
'9':('w','x','y','z')}
def letterCombinations(self, digits: str) -> List[str]:
a = [Solution.digit2letter[d] for d in digits]
r = ['']
for i in range(len(a)):
r = [s+c for c in a[i]
for s in r]
return [] if len(r)==1 else r # cannot return ['']
从一个初始状态开始，一层层循环构建，每一层循环，都利用了上一次计算的结果。这个思路类似DP算法，但是这里有个坑，如果此题的digit很长很长，采用此思路，保存中间状态所需要的空间会非常庞大，空间复杂度太高！
static unordered_map<char,string> digit2letter \
{{'2',"abc"},
{'3',"def"},
{'4',"ghi"},
{'5',"jkl"},
{'6',"mno"},
{'7',"qprs"},
{'8',"tuv"},
{'9',"wxyz"}};
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> r;
if(digits == "")
return r;
r.reserve(64);
for(auto c: digit2letter[digits[0]])
r.emplace_back(1,c);
vector<string> m;
m.reserve(64);
for(auto d: digits.substr(1)){
m.clear();
for(size_t i{}; i<r.size(); ++i)
for(auto c: digit2letter[d])
m.emplace_back(r[i]+c);
swap(r,m);
}
return r;
}
};
由于类型的原因，unordered_map的key是char型。to_string不能支持char类型，char类型会被当做int来处理，比较坑！
const static char *d2s[] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
const static char d2slen[] = {3,3,3,3,3,4,3,4};
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
char ** letterCombinations(char * digits, int* returnSize){
if(digits[0] == 0){
*returnSize = 0;
return NULL;
}
int ndigit = strlen(digits);
int ndigitp1 = ndigit + 1;
#define I(i) (digits[i]-'2')
*returnSize = d2slen[I(0)];
for(int i=1; i<ndigit; ++i)
*returnSize *= d2slen[I(i)];
char (*mr)[ndigitp1] = calloc(*returnSize, ndigitp1);
int mrsize = d2slen[I(0)];
for(int i=0; i<mrsize; ++i)
mr[i][0] = d2s[I(0)][i];
char (*mr2)[ndigitp1] = calloc(*returnSize, ndigitp1);
for(int i=1; i<ndigit; ++i){
int mr2size = 0;
for(int j=0; j<mrsize; ++j){
for(int k=0; k<d2slen[I(i)]; ++k){
memcpy(mr2[mr2size], mr[j], i);
mr2[mr2size][i] = d2s[I(i)][k];
++mr2size;
}
}
memcpy(mr, mr2, mr2size*ndigitp1);
mrsize = mr2size;
memset(mr2, 0, mr2size*ndigitp1);
}
free(mr2);
#undef I
char **r = malloc(sizeof(char*)*(*returnSize));
for(int i=0; i<*returnSize; ++i){
r[i] = malloc(ndigitp1);
memcpy(r[i], mr[i], ndigitp1);
}
free(mr);
return r;
}
char*，mr指向char [ndigitp1]！本题的技能点是Backtracking，这个point有点意思：这类递归实现，本质上是将循环递归化。而递归化的原因，是循环嵌套深度的不确定，它是个参数，无法提前写出nested loop的代码。
时间复杂度为：\(O(M^N)\)，M为输入中各个组合的元素个数的最大值，N为输入组合的个数。这类算法，M和N的值都不能太大！
回溯虽然使用了递归，但是空间复杂度相比前一个算法，大大降低！如果不算递归消耗的栈空间，那么空间复杂度就是\(O(1)\)。不再保存大量的中间结果，每个中间结果，都直接以参数的形式进行传递。
class Solution:
digit2letter = {'2':('a','b','c'),
'3':('d','e','f'),
'4':('g','h','i'),
'5':('j','k','l'),
'6':('m','n','o'),
'7':('p','q','r','s'),
'8':('t','u','v'),
'9':('w','x','y','z')}
def letterCombinations(self, digits: str) -> List[str]:
def _backtrack(i, t):
if i == n:
r.append(t)
return
for c in Solution.digit2letter[digits[i]]:
_backtrack(i+1, t+c)
n = len(digits)
r = []
_backtrack(0, '')
return [] if n==0 else r
Backtracking的感觉在这里：一层层递归深入，先得到一个解后，再返回上一层，然后再深入，再返回......这就是回溯！回溯就是先一口气找到一个解，然后回到前面某个地方（递归调用返回的地方），找下一个解！
static unordered_map<char,string> digit2letter \
{{'2',"abc"},
{'3',"def"},
{'4',"ghi"},
{'5',"jkl"},
{'6',"mno"},
{'7',"qprs"},
{'8',"tuv"},
{'9',"wxyz"}};
class Solution {
string digits;
int size;
vector<string> r;
void backtrace(int level, string s){
if(level == size){
this->r.push_back(s);
return;
}
for(auto c: digit2letter[digits[level]])
backtrace(level+1, s+c);
}
public:
vector<string> letterCombinations(string digits) {
this->r.clear();
if(digits == "")
return this->r;
this->digits = digits;
this->size = digits.size();
backtrace(0, "");
return this->r;
}
};
const static char *d2s[] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
const static char d2slen[] = {3,3,3,3,3,4,3,4};
void _backtrack(int level, char *digits, int ndigit,
char **r, int *idx, char *p){
if(level == ndigit){
p[level] = 0;
strcpy(r[(*idx)++], p);
return;
}
int i = digits[level] - '2';
for(int j=0; j<d2slen[i]; ++j){
p[level] = d2s[i][j];
_backtrack(level+1, digits, ndigit,
r, idx, p);
}
}
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
char ** letterCombinations(char * digits, int* returnSize){
if(digits[0] == 0){
*returnSize = 0;
return NULL;
}
int ndigit = strlen(digits);
int ndigitp1 = ndigit + 1;
*returnSize = d2slen[digits[0]-'2'];
for(int i=1; i<ndigit; ++i)
*returnSize *= d2slen[digits[i]-'2'];
char **r = malloc(sizeof(char*)*(*returnSize));
for(int i=0; i<*returnSize; ++i)
r[i] = malloc(ndigitp1);
char *p = malloc(ndigitp1);
int idx = 0;
_backtrack(0, digits, ndigit,
r, &idx, p);
free(p);
return r;
}
本文链接：https://cs.pynote.net/ag/leetcode/202310101/
-- EOF --
-- MORE --