leetcode 17. Letter Combinations of a Phone Number

来源:互联网 发布:idm下载器破解版 mac 编辑:IT博客网 时间:2019/12/11 23:05

题意

给定一个数字字符串,枚举各个数字对应的字母组合后的字符串(不重复)。

题解

一个串中字母的重复次数,即后面字母形成串的可能种数。
给定数字”234”,对应串“abc”、“def”、“ghi”,所有可能的串的种数是3 * 3 * 3 = 27;
第一个串的每个字母的重复次数为:len(“def”) * len(“ghi”) = 9,第二、第三个串以此类推。

代码

class Solution {public:    vector<string> letterCombinations(string digits) {        // map<char, string> dict;{('2',"abc"), ('3',"def"), ('4', "ghi"), ('5', "jkl"), ('6', "mno"),        //                          ('7', "pqrs"), ('8', "tuv"), ('9', "wxyz") };        const int MAXSIZE = 10;        string dict[MAXSIZE] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};        if (digits.length() == 0)        {            vector<string> temp;            return temp;        }        int len = digits.length();        int result_size = 1;         vector<string> strs;        vector<int> strs_len;        for (int i = 0; i < len; i++)        {            string temp = dict[digits[i] - '0'];            strs.push_back(temp);            strs_len.push_back(temp.length());            result_size *= temp.length(); //calu the all conditions        }        int repeated_size = result_size;        vector<string> result(result_size);        for (int i = 0; i < len; i++)        {            repeated_size = repeated_size / strs_len[i]; //当前串中各个字母的重复次数,即后面字母形成一个串的可能种数            int index = 0;            while (index < result_size)            {                for (int j = 0; j < strs_len[i]; j++)                {                    for (int k = 0; k < repeated_size; k++)                    {                        string temp = result[index] + strs[i][j];                        result[index++] += strs[i][j];                    }                }            }        }        vector<string> unique_res;        set<string> temp;        for (int i = 0; i < result.size(); i++)        {            if (!temp.count(result[i]))            {                unique_res.push_back(result[i]);                temp.insert(result[i]);            }        }        //return result;        return unique_res;    }};
0 0