leetcode_20 Letter Combinations of a Phone Number

题目：

电话号码的字母组合

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

方法解析：

Approach 1: Backtracking

Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.    回溯法是通过挖掘所有潜在候选者，来找到所有的问题解决方案的算法。如果潜在的候选者不在解决方案中，或者，不在解决方案的最后一步，回溯算法将丢弃该解决方案，通过改变前一步的回溯，然后重试。

Here is a backtrack function backtrack(combination, next_digits) which takes as arguments an ongoing letter combination and the next digits to check.

• If there is no more digits to check that means that the current combination is done.
• If there are still digits to check :
  • Iterate over the letters mapping the next available digit.
    • Append the current letter to the current combination combination = combination + letter.
    • Proceed to check next digits : backtrack(combination + letter, next_digits[1:]).

class Solution {
public:unordered_map<string,string> phone = {{"2","abc"},{"3","def"},{"4","ghi"},{"5","jkl"},{"6","mno"},{"7","pqrs"},{"8","tuv"},{"9","wxyz"}};vector<string> output;void backtrace(string combination,string next_digits){if(next_digits.length() == 0){output.push_back(combination);}else{string digit = next_digits.substr(0,1);string letters = phone[digit];for(int i = 0; i < letters.length(); i++){string letter = letters.substr(i,1);backtrace(combination + letter,next_digits.substr(1));}}}vector<string> letterCombinations(string digits) {if(digits.length() != 0)backtrace("",digits);return output;}};