C++ 面试题翻译电话号码实例代码题目要求实现一个能够将电话号码翻译成字母的程序。具体来讲,即是将类似于"23"这样的数字字符串翻译成所有可能的字母组合,其中 '2' 可以代表 'a', 'b', 'c', '3' 可以代表 'd', 'e', 'f',以此类推,直到 '9' 可以代表 'w', 'x', 'y', 'z'。对于一个包含多个数字的字符串,其可能的字母组合数目是不确定的,所以需要我们编程来实现。
思路分析
为了翻译电话号码,我们可以采用回溯算法。我们从数字字符串的第一个数字开始逐个遍历,每一次遍历选中一个数字所代表的所有字母中的一个,再进一步递归处理剩余的数字。这样一直到所有数字被选中,我们就得到了当前数字串所对应的所有字母组合。
代码实现
以下是参考实现:
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) {
return {};
}
vector<string> res;
string path;
unordered_map<char, string> phoneMap = {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
dfs(digits, 0, path, phoneMap, res);
return res;
}
private:
void dfs(string& digits, int index, string& path, unordered_map<char, string>& phoneMap, vector<string>& res) {
if (index == digits.size()) {
res.push_back(path);
return;
}
for (char c : phoneMap[digits[index]]) {
path.push_back(c);
dfs(digits, index + 1, path, phoneMap, res);
path.pop_back();
}
}
};
其中,我们首先新建一个unordered_map来存储数字字符表示的所有可能的字母组合,然后我们从digits的第0个字符开始,使用dfs递归进行搜索遍历。对于当前遍历到的digit[index],我们将其所有的字母组合代表的字符都一个一个试一遍,并递归调用dfs函数去处理digits[index+1]之后的数字字符。
示例说明
以下是两个示例:
输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
输入:digits = ""
输出:[]
以上就是本题的完整攻略,包括了思路分析和代码实现。如果有具体问题,欢迎进一步讨论。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++ 面试题翻译电话号码实例代码 - Python技术站