[LeetCode]Letter Combinations of a Phone Number题解

Letter Combinations of a Phone Number:

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.

简单讲讲这道题的思路吧。一开始想到的方法是，由给定的digits字符串的每个字符，确定对应的若干个（3或4）字符，然后通过递归，从底层开始，每次将这一层的字符和vector中的字符串组合一下，再返回给上一层。

思路是挺清晰也挺简单的，不过c++实现过程中也遇到了一点困难。

char转换成string的问题。递归最底层要实现这个，“”+ ch并不能做到转string，最后是用一个空的string，push_back字符得到想要的结果。
digits的字符对应若干个字符的问题。由于太久没有写这些东西，脑子不是很清晰，一开始也写错了，最终跟这个相关的代码也是有些乱的。

第二种是非递归的方法，每次把数字对应的3或4个字符添加到结果集合中。

最后有给出python实现的代码，非递归，非常简单。

class Solution {

public:

    vector<string> letterCombinations(string digits) {

        return combine(digits,0);

    }

    std::vector<string> combine(string digits,int len){

        vector<string>  re,temp;

        //threeOrFour：这个字符对应着几个字符；

        //ext：为了7（对应4个字符）以后的数字对应字符都+了1而定义的int，值是0或1

        int threeOrFour,ext;

        if(digits[len] == '7' || digits[len] == '9'){

            threeOrFour = 4;

        }else{

            threeOrFour = 3;

        }

        if(digits[len] > '7'){

            ext = 1;

        }else{

            ext = 0;

        }

        //ch是该数字对应的第一个字符

        char ch = (digits[len] - 48) * 3 + 91 + ext;

        string empty = "";

        if ( len < digits.size()){

            temp = combine(digits,len+1);

        }

        //递归的最底层

        if (len == digits.size() - 1){

            string t;

            for(int i = 0; i < threeOrFour; i++){

                t = empty;

                t.push_back(ch+i);

                re.push_back(t);

            }

            return re;

        }

        else{

            for (int i = 0; i < temp.size(); ++i){

                for(int j = 0; j < threeOrFour; j++){

                    string str = empty;

                    str.push_back(ch + j);

                    re.push_back((str+temp[i]));

                }

            }

            return re;

        }

    }

};

下面是修改之后，更加简洁的版本：

class Solution {

private:

    string letters[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public:

    vector<string> letterCombinations(string digits) {

        return Mycombine(digits,0);

    }

    vector<string> Mycombine(string digits,int len){

        std::vector<string> re, temp;

        temp.push_back("");

        if(digits.empty()) return re;

        if(len < digits.size() - 1){

            temp = Mycombine(digits,len+1);

        }

        string get = letters[toInt(digits[len])];

        for (int i = 0; i < temp.size(); ++i){

            for (int j = 0; j < get.size(); ++j){

                string put ="";

                put.push_back(get[j]);

                put += temp[i];

                re.push_back(put);

            }

        }

        return re;

    }

    int toInt(char ch){

        return ch - 48;

    }

};

迭代方法：

class Solution {

private:

    string letters[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public:

    vector<string> letterCombinations(string digits) {

        std::vector<string> re,temp;

        if(digits.empty()) return re;

        re.push_back("");

        //temp.push_back("");

        for(int i = 0; i < digits.size(); i++){

            string get = letters[toInt(digits[i])];

            for(int j = 0; j < re.size(); j++){

                string t = re[j];

                for(int k = 0; k < get.size(); k++){

                    string str = t;

                    str.push_back(get[k]);

                    temp.push_back(str);

                }

            }

            re = temp;

            temp.clear();

        }

        return re;

    }

    int toInt(char ch){

        return ch - 48;

    }

};

事实上，用python的话非常好实现，而且逻辑很清晰：

class Solution:

    def letterCombinations(self, digits):

        """

        :type digits: str

        :rtype: List[str]

        """

        if len(digits) == 0:

            return []

        re = ['']

        chars = ['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']

        m = {i:[ch for ch in chars[i]] for i in range(0,10)}

        data = [int(digits[i]) for i in range(len(digits)) ]    

        for i in data:

            temp = []

            for s in re:

                for j in m[i]:

                    temp.append(s + j)

                    print(j)

            re = temp

        return re

巴特西

[LeetCode]Letter Combinations of a Phone Number题解

最新文章

热门文章