当前位置: 首页> 科技> 能源 > 192.回溯算法:电话号码的字母组合(力扣)

192.回溯算法:电话号码的字母组合(力扣)

时间:2025/7/13 5:00:41来源:https://blog.csdn.net/weixin_63779802/article/details/139888796 浏览次数:2次

代码解决

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个字符开始生成组合。
    • 返回结果向量。

运行逻辑

  1. 从输入字符串的第一个字符开始,根据其对应的字母映射,依次尝试所有可能的字母。
  2. 对每个字母,递归处理下一个字符,直到生成一个完整的组合。
  3. 每生成一个完整的组合,就将其添加到结果向量中。
  4. 回溯,尝试其他可能的字母组合。

这个回溯算法的时间复杂度是 O(3^n * 4^m),其中 n 是对应 3 个字母的数字(如 2、3、4、5、6、8)的个数,m 是对应 4 个字母的数字(如 7、9)的个数。这个复杂度源于每个数字对应的字母数量及其组合的所有可能性。

关键字:192.回溯算法:电话号码的字母组合(力扣)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: