本文主要是介绍192.回溯算法:电话号码的字母组合(力扣),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
代码解决
class Solution { public:// 定义每个数字对应的字母映射const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz" // 9};string s; // 用于存储当前的组合vector<string> result; // 用于存储所有的组合结果// 回溯函数void backtracing(string digits, int index) {// 如果索引等于输入字符串的长度,说明生成了一个完整的组合if (index == digits.size()) {result.push_back(s); // 将当前组合添加到结果集中return;}// 获取当前数字对应的字母字符串int dig = digits[index] - '0'; // 将字符转换为整数string letter = letterMap[dig]; // 获取对应的字母字符串// 遍历每个字母,进行回溯for (int i = 0; i < letter.size(); i++) {s.push_back(letter[i]); // 将当前字母添加到组合中backtracing(digits, index + 1); // 递归调用,生成下一层的组合s.pop_back(); // 回溯,移除最后一个添加的字母}}// 主函数vector<string> letterCombinations(string digits) {// 如果输入字符串为空,直接返回空结果if (digits.size() == 0) {return result;}// 调用回溯函数,从第0个字符开始backtracing(digits, 0);return result;} };
成员变量
const string letterMap[10]
:一个字符串数组,用于存储每个数字(0-9)对应的字母映射。string s
:一个字符串,用于存储当前生成的字母组合。vector<string> result
:一个字符串向量,用于存储所有生成的字母组合。回溯函数:
void backtracing(string digits, int index)
参数:
string digits
:输入的电话号码字符串。int index
:当前处理的字符索引。逻辑:
- 结束条件:
if (index == digits.size())
:
- 如果当前索引等于输入字符串的长度,说明生成了一个完整的组合,将其添加到结果集中。
- 获取当前数字对应的字母字符串:
int dig = digits[index] - '0'
:将字符转换为整数。string letter = letterMap[dig]
:获取当前数字对应的字母字符串。- 遍历每个字母,进行回溯:
for (int i = 0; i < letter.size(); i++)
:遍历当前字母字符串的每个字母。s.push_back(letter[i])
:将当前字母添加到组合中。backtracing(digits, index + 1)
:递归调用,处理下一个字符。s.pop_back()
:回溯,移除最后一个添加的字母,以便尝试其他字母。主函数:
vector<string> letterCombinations(string digits)
- 逻辑:
- 如果输入字符串为空,直接返回空的结果向量。
- 调用回溯函数,从第0个字符开始生成组合。
- 返回结果向量。
运行逻辑
- 从输入字符串的第一个字符开始,根据其对应的字母映射,依次尝试所有可能的字母。
- 对每个字母,递归处理下一个字符,直到生成一个完整的组合。
- 每生成一个完整的组合,就将其添加到结果向量中。
- 回溯,尝试其他可能的字母组合。
这个回溯算法的时间复杂度是 O(3^n * 4^m),其中 n 是对应 3 个字母的数字(如 2、3、4、5、6、8)的个数,m 是对应 4 个字母的数字(如 7、9)的个数。这个复杂度源于每个数字对应的字母数量及其组合的所有可能性。
这篇关于192.回溯算法:电话号码的字母组合(力扣)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!