0017._Letter_Combinations_of_a_Phone_Number.md

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