Skip to content

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;
    }
};


回到顶部