17. Letter Combinations of a Phone Number-白红宇

17. Letter Combinations of a Phone Number

阅读量：4259 次

发布时间：2019-05-26

本文共 1644 字，大约阅读时间需要 5 分钟。

Given a digit string, 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.

Input:Digit string “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.

思路1：利用一个递归遍历

unordered_map
   
     data = { { '2', "abc" }, { '3', "def" },  { '4', "ghi" }, { '5', "jkl" }, { '6', "mno" }, { '7', "pqrs" }, { '8', "tuv" }, { '9', "wxyz" } };void dfs_letter(string &digits, int pos,string str, vector
    
     & res){    if (str.size() == digits.size()){        res.push_back(str);        return;    }    for (int i = 0; i < data[digits[pos]].size(); i++){        dfs_letter(digits, pos + 1, str + data[digits[pos]][i], res);    }}vector
     
       letterCombinations1(string digits) {    vector
      
        str;    if (digits == "")return str;    dfs_letter(digits, 0, "", str);    return str;}

思路2：利用一个循环过程

unordered_map
   
     data = { { '2', "abc" }, { '3', "def" },  { '4', "ghi" }, { '5', "jkl" }, { '6', "mno" }, { '7', "pqrs" }, { '8', "tuv" }, { '9', "wxyz" } };vector
    
      letterCombinations(string digits) {    vector
     
       str;    if (digits == "")return str;    vector
      
        v({ "" });    for (int i = 0; i < digits.size(); i++){        vector
       
         temp;        for (int j = 0; j < v.size(); j++){            for (int k = 0; k < data[digits[i]].size(); k++){                temp.push_back(v[j] + data[digits[i]][k]);            }        }        v = temp;    }    return v;}