LeetCode C++24-电话号码的字母组合

题目描述

leetcode原题链接：电话号码的字母组合

给定一个仅包含2-9的字符串，返回所有它能表示的字母组合。答案可以按任何顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。

举例

示例 1：输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：输入：digits = "" 输出：[]
示例 3：输入：digits = "2" 输出：["a","b","c"]

解题方法：回溯搜索

代码

#include 
#include 
#include 
#include 

void backtrack(std::vector& result, 
		  std::map& mp,
		  const std::string& nums,
		  std::string& str) {
	if (str.size() == nums.size()) {
		result.push_back(str);
	}
	int idx = str.size();// 每次向str加入一个元素后，相当于++idx
	char key = nums[idx];//从nums获取对应的mp的key
	std::string candidates = mp[key];
	for (char ch : candidates) { //回溯搜索的核心代码
		str.push_back(ch);
		backtrack(result, mp, nums, str);
		str.pop_back();
	}
}

std::vector digit_combination(const std::string& nums) {
	std::vector result;
	std::map mp = {
		{'2', "abc"},
		{'3', "def"},
		{'4', "ghi"},
		{'5', "jkl"},
		{'6', "mno"},
		{'7', "pqrs"},
		{'8', "tuv"},
		{'9', "wxyz"}
	};
	std::string str("");
	backtrack(result, mp, nums, str);
	return result;
}

void print_result(const std::string&nums, 
				  const std::vector& result) {
	std::cout << "========" << std::endl;
	std::cout << "input:" << std::endl;
	for (auto num : nums) {
		std::cout << num << " ";
	}
	std::cout << std::endl;
	std::cout << "output:" << std::endl;
	for (auto& str : result) {
		std::cout << str << std::endl;
	}
}

int main()
{
	// nums="23" ==> ["ad,"ae","af","bd","be","bf","cd","ce","cf"]
	std::string nums = "23";
	std::vector result = digit_combination(nums);
	print_result(nums, result);
	// nums="" ==> []
	nums = "";
	result = digit_combination(nums);
	print_result(nums, result);
	// nums="2" ==>["a","b","c"]
	nums = "2";
	result = digit_combination(nums);
	print_result(nums, result);
    return 0;
}

代码运行结果如下：

========
input:
2 3 
output:
ad
ae
af
bd
be
bf
cd
ce
cf
========
input:

output:

========
input:
2 
output:
a
b
c

LeetCode C++24-电话号码的字母组合

C/C++/C#相关栏目本月热门文章