【Letter Combinations of a Phone Number】cpp

题目：

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.

代码：

class Solution {

public:

    vector<string> letterCombinations(string digits) {

            vector<string> ret;

            if ( digits.empty() ) return ret;

            map<int, string> digitLetters;

            digitLetters[] = "";

            digitLetters[] = "";

            digitLetters[] = "abc";

            digitLetters[] = "def";

            digitLetters[] = "ghi";

            digitLetters[] = "jkl";

            digitLetters[] = "mno";

            digitLetters[] = "pqrs";

            digitLetters[] = "tuv";

            digitLetters[] = "wxyz";

            vector<int> letterBegin(,);

            int index = ;

            string tmp;

            Solution::combine(ret, tmp, index, digits, digitLetters, letterBegin);

            return ret;

    }

    static void combine(

        vector<string>& ret,

        string& tmp,

        int index,

        string& digits,

        map<int,string>& digitLetters,

        vector<int>& letterBegin)

    {

            if (index==digits.size())

            {

                ret.push_back(tmp);

                return;

            }

            int curr = digits[index]-'';

            string letters = digitLetters[curr];

            for ( int i = ; i < letters.size(); ++i )

            {

                letterBegin[curr] = i;

                tmp.push_back(letters[i]);

                Solution::combine(ret, tmp, index+, digits, digitLetters, letterBegin);

                tmp.erase(tmp.end()-);

            }

    }

};

tips：

上述的代码是AC的。思路也就是常规dfs的思路：

1. 终止条件是层级到了digits的长度

2. 每一层递归相当于根据该位置的数字选一个字母

但是，个人感觉这道题的题干要求没说清楚；既然是letter combinations，而不是letter permutation，那么“ac”和“ca”就应该算一个combination，但是OJ之后发现默认“ac”和“ca”算两个。加入“ac”和“ca”算一个，有没有解法呢？代码如下：

class Solution {

public:

    vector<string> letterCombinations(string digits) {

            vector<string> ret;

            if ( digits.empty() ) return ret;

            map<int, string> digitLetters;

            digitLetters[] = "";

            digitLetters[] = "";

            digitLetters[] = "abc";

            digitLetters[] = "def";

            digitLetters[] = "ghi";

            digitLetters[] = "jkl";

            digitLetters[] = "mno";

            digitLetters[] = "pqrs";

            digitLetters[] = "tuv";

            digitLetters[] = "wxyz";

            vector<int> letterBegin(,);

            int index = ;

            string tmp;

            Solution::combine(ret, tmp, index, digits, digitLetters, letterBegin);

            return ret;

    }

    static void combine(

        vector<string>& ret,

        string& tmp,

        int index,

        string& digits,

        map<int,string>& digitLetters,

        vector<int>& letterBegin)

    {

            if (index==digits.size())

            {

                ret.push_back(tmp);

                return;

            }

            int curr = digits[index]-'';

            string letters = digitLetters[curr];

            for ( int i = letterBegin[curr]; i < letters.size(); ++i )

            {

                letterBegin[curr] = i;

                tmp.push_back(letters[i]);

                Solution::combine(ret, tmp, index+, digits, digitLetters, letterBegin);

                tmp.erase(tmp.end()-);

            }

    }

};

tips：

多维护一个letterBegin的数组，标记“当前的组合中，某个数字对应的字母序列中应该从第几个字母开始取”。

如果输入是“22”，那么给出的解集就是：

从这个例子可以看出来，算法的原理就是维护某一个数字对应字母序列：如果数字重复出现，那么对应的字母要保证字典序递增，这样就不会用重复的。

可惜题目并不是这么要求的。

===============================================

既然题目要求简单了，则再追求一个迭代的解法。AC的代码如下：

class Solution {

public:

    vector<string> letterCombinations(string digits) {

            vector<string> ret;

            if (digits.empty()) return ret;

            ret.push_back("");

            map<int, string> digitLetters;

            digitLetters[] = "abc";

            digitLetters[] = "def";

            digitLetters[] = "ghi";

            digitLetters[] = "jkl";

            digitLetters[] = "mno";

            digitLetters[] = "pqrs";

            digitLetters[] = "tuv";

            digitLetters[] = "wxyz";

            for ( size_t i = ; i < digits.size(); ++i )

            {

                int curr = digits[i]-'';

                string letters = digitLetters.find(curr)==digitLetters.end() ? "" : digitLetters[curr];

                vector<string> tmp = ret;

                ret.clear();

                for ( size_t j = ; j < tmp.size(); ++j )

                {

                    for ( size_t k = ; k < letters.size(); ++k )

                    {

                        string ori = tmp[j];

                        ori += letters[k];

                        ret.push_back(ori);

                    }

                }

            }

            return ret;

    }

};

完毕。

======================================

第二次过这道题，用dfs过的。注意如果原来的digits==""返回的也是空。

class Solution {

public:

        vector<string> letterCombinations(string digits)

        {

            map<char, string> digit_letters;

            digit_letters[''] = "abc";

            digit_letters[''] = "def";

            digit_letters[''] = "ghi";

            digit_letters[''] = "jkl";

            digit_letters[''] = "mno";

            digit_letters[''] = "pqrs";

            digit_letters[''] = "tuv";

            digit_letters[''] = "wxyz";

            vector<string> ret;

            if ( digits=="" ) return ret;

            vector<char> tmp;

            Solution::dfs(ret, digits, tmp, digit_letters);

            return ret;

        }

        static void dfs(

            vector<string>& ret,

            string digits,

            vector<char>& tmp,

            map<char,string>& digit_letters)

        {

            if ( tmp.size()==digits.size() )

            {

                ret.push_back(string(tmp.begin(),tmp.end()));

                return;

            }

            int index = tmp.size();

            for ( int i=; i<digit_letters[digits[index]].size(); ++i )

            {

                tmp.push_back(digit_letters[digits[index]][i]);

                Solution::dfs(ret, digits, tmp, digit_letters);

                tmp.pop_back();

            }

        }

};

巴特西

【Letter Combinations of a Phone Number】cpp

最新文章

热门文章