leetcode 17. Letter Combinations of a Phone Number

小鱼儿 2022-07-28 00:27 180阅读 0赞

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.

![200px-Telephone-keypad2.svg.png][]

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 {
    	map<int, vector<char>>num2char;
    	void init()
    	{
    		num2char[2].push_back('a');
    		num2char[2].push_back('b');
    		num2char[2].push_back('c');
    		num2char[3].push_back('d');
    		num2char[3].push_back('e');
    		num2char[3].push_back('f');
    		num2char[4].push_back('g');
    		num2char[4].push_back('h');
    		num2char[4].push_back('i');
    		num2char[5].push_back('j');
    		num2char[5].push_back('k');
    		num2char[5].push_back('l');
    		num2char[6].push_back('m');
    		num2char[6].push_back('n');
    		num2char[6].push_back('o');
    		num2char[7].push_back('p');
    		num2char[7].push_back('q');
    		num2char[7].push_back('r');
    		num2char[7].push_back('s');
    		num2char[8].push_back('t');
    		num2char[8].push_back('u');
    		num2char[8].push_back('v');
    		num2char[9].push_back('w');
    		num2char[9].push_back('x');
    		num2char[9].push_back('y');
    		num2char[9].push_back('z');
    		
    	}
    	void do_once(vector<string>&re, string digits)
    	{
    		vector<string>newre;
    		for (int i = 0; i < re.size(); i++)
    		{
    			for (int j = 0; j < num2char[digits[0] - '0'].size(); j++)
    			{
    				string str = re[i];
    				str += num2char[digits[0] - '0'][j];
    				newre.push_back(str);
    			}
    		}
    		re = newre;
    	}
    public:
    	vector<string> letterCombinations(string digits) {
    		vector<string>re;
    		if (digits.empty())
    			return re;
    		init();
    		re.push_back("");
    		while (!digits.empty())
    		{
    			do_once(re, digits);
    			digits.erase(0, 1);
    		}
    		return re;
    	}
    };

accepted

[200px-Telephone-keypad2.svg.png]: /images/20220727/76c61f2ea0f34c7399d8292cc3765fa5.png