leetcode解題報告17. Letter Combinations of a Phone Number

題目位址

難度是easy

題目描述

在手機９個數字格裡，其實一個數字對應幾個字母的。其對應關系如下(為了友善，直接代碼形式給出，比較容易了解看懂)

my_map['0'] = ' ';
my_map['2'] = "abc";
my_map['3'] = "def";
my_map['4'] = "ghi";
my_map['5'] = "jkl";
my_map['6'] = "mno";
my_map['7'] = "pqrs";
my_map['8'] = "tuv";
my_map['9'] = "wxyz";
           

現在是輸入一個數字組成的字元串，找出所有對應的可能的字母字元串。

例子如下：

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

我的思路

是一個模拟類的題目，直接枚舉列出來就行了。問題是如何枚舉。直接嘗試用for循環會發現這很不适合這個問題。可以發現這其實類似與深搜的過程，而for循環更适合廣搜的過程。對于深搜的過程，可以考慮用遞歸的方式。

我的代碼

#include <map>

using namespace std;

class Solution {
public:
    map<char, string> my_map;

    Solution(){
            my_map['0'] = ' ';
    my_map['2'] = "abc";
    my_map['3'] = "def";
    my_map['4'] = "ghi";
    my_map['5'] = "jkl";
    my_map['6'] = "mno";
    my_map['7'] = "pqrs";
    my_map['8'] = "tuv";
    my_map['9'] = "wxyz";
    }
    void func(string& s, int index, vector<string>& result, string cur) {
        if (index == s.size()-) {
            for (int i = ; i < my_map[s[index]].size(); i++) {
                result.push_back(cur+my_map[s[index]][i]);
            }
            return;
        }
        for (int i = ; i < my_map[s[index]].size(); i++) {
            func(s, index+, result, cur+my_map[s[index]][i]);    
        }


    }
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if (digits.size() == ) {
            return result;
        }
        func(digits, , result, "");
        return result;
    }
};
           

閱讀官方題解

沒有官方題解，思路差不多。其實用for循環還是比較友善地處理的，沿這數字字元串走，下一步的結果就是目前結果集和下一個數字字元對應的字元字元集的一個笛卡爾集。

思想核心總結

注意分析問題，深搜的過程可以考慮用遞歸的方式。