17. Letter Combinations of a Phone Number
难度:Medium
刷题内容
原题连接
- https://leetcode.com/problems/letter-combinations-of-a-phone-number/
内容描述
Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.
Example:
Input: "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.
˼·1 **- ʱ�临�Ӷ�: O(2^n)*- �ռ临�Ӷ�: O(1)***
�û��ݷ�ȥ�⣬�Ƚ������ַ���ת�����֡�����7��9֮内容描述��ֶ���3����ĸ�������ÿ�����ִ�������ĸ内容描述�û��ݷ�
class Solution {
public:
void DFS(string& s,int i,vector<string>& ans,string& temp)
{
if(i == s.length())
{
ans.push_back(temp);
return;
}
int t = s[i] - '2';
int ch_beg;
if(t < 6)
ch_beg = 'a' + t * 3;
else
ch_beg = 'a' + (t - 1) * 3 + 4;
int en = 3;
if(t == 5 || t == 7)
en = 4;
for(int j = 0;j < en;++j)
{
temp.push_back(ch_beg + j);
DFS(s,i + 1,ans,temp);
temp.pop_back();
}
}
vector<string> letterCombinations(string digits) {
vector<string> ans;
if(!digits.size())
return ans;
string temp;
DFS(digits,0,ans,temp);
return ans;
}
};
