C++怎么解決電話號碼的字母組合問題

155次閱讀

共計 1962 個字符，預計需要花費 5 分鐘才能閱讀完成。

這篇文章主要介紹“C++ 怎么解決電話號碼的字母組合問題”的相關知識，丸趣 TV 小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“C++ 怎么解決電話號碼的字母組合問題”文章能幫助大家解決問題。

電話號碼的字母組合

Given a string containing digits from 2-9inclusive, 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.

這道題讓我們求電話號碼的字母組合，即數(shù)字 2 到 9 中每個數(shù)字可以代表若干個字母，然后給一串數(shù)字，求出所有可能的組合。這里可以用遞歸 Recursion 來解，需要建立一個字典，用來保存每個數(shù)字所代表的字符串，然后還需要一個變量 level，記錄當前生成的字符串的字符個數(shù)，實現(xiàn)套路和上述那些題十分類似。在遞歸函數(shù)中首先判斷 level，如果跟 digits 中數(shù)字的個數(shù)相等了，將當前的組合加入結果 res 中，然后返回。我們通過 digits 中的數(shù)字到 dict 中取出字符串，然后遍歷這個取出的字符串，將每個字符都加到當前的組合后面，并調用遞歸函數(shù)即可，參見代碼如下：

解法一：

class Solution {
public:
 vector string  letterCombinations(string digits) { if (digits.empty()) return {};
 vector string  res;
 vector string  dict{ ,  ,  abc ,  def ,  ghi ,  jkl ,  mno ,  pqrs ,  tuv ,  wxyz 
 letterCombinationsDFS(digits, dict, 0,  , res);
 return res;
 }
 void letterCombinationsDFS(string  digits, vector string  dict, int level, string out, vector string  res) { if (level == digits.size()) {res.push_back(out); return;}
 string str = dict[digits[level] -  0 
 for (int i = 0; i   str.size(); ++i) { letterCombinationsDFS(digits, dict, level + 1, out + str[i], res);
 }
 }
};

這道題也可以用迭代 Iterative 來解，在遍歷 digits 中所有的數(shù)字時，先建立一個臨時的字符串數(shù)組 t，然后跟上面解法的操作一樣，通過數(shù)字到 dict 中取出字符串 str，然后遍歷取出字符串中的所有字符，再遍歷當前結果 res 中的每一個字符串，將字符加到后面，并加入到臨時字符串數(shù)組 t 中。取出的字符串 str 遍歷完成后，將臨時字符串數(shù)組賦值給結果 res，具體實現(xiàn)參見代碼如下：

解法二：

class Solution {
public:
 vector string  letterCombinations(string digits) { if (digits.empty()) return {};
 vector string  res{ 
 vector string  dict{ ,  ,  abc ,  def ,  ghi ,  jkl ,  mno ,  pqrs ,  tuv ,  wxyz 
 for (int i = 0; i   digits.size(); ++i) {
 vector string  t;
 string str = dict[digits[i] -  0 
 for (int j = 0; j   str.size(); ++j) { for (string s : res) t.push_back(s + str[j]);
 }
 res = t;
 }
 return res;
 }
};

關于“C++ 怎么解決電話號碼的字母組合問題”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關的知識，可以關注丸趣 TV 行業(yè)資訊頻道，丸趣 TV 小編每天都會為大家更新不同的知識點。

正文完