17. 电话号码的字母组合

一、题目描述

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

17. 电话号码的字母组合

二、示例

示例 1:

输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2:

输入:digits = ""
输出:[]

示例 3:

输入:digits = "2"
输出:["a","b","c"]

三、输入输出说明

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

四、基本思路

1)首先得到当前数字对应的字符串str

2)查询当前生成字母组合ans的第一个元素tmp(即生成字符串数组的第一个元素)

3)将1)中得到的str每个元素分别加到tmp尾部,然后添加至生成字母组合ans数组中

4)当3)遍历str结束时删除ans的第一个元素,从而更新tmp

5)循环结束条件为ans的第一个元素tmp的字符串长度大于当前数字digits下标(意味着要添加下一个数字对应的字母)

五、代码

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        ans.clear();
        if (digits.length() == 0) {
            return ans;
        }
        map<char, string> mcs;
        mcs['2'] = "abc";
        mcs['3'] = "def";
        mcs['4'] = "ghi";
        mcs['5'] = "jkl";
        mcs['6'] = "mno";
        mcs['7'] = "pqrs";
        mcs['8'] = "tuv";
        mcs['9'] = "wxyz";
        ans.push_back("");
        for (int i = 0; i < digits.length(); i++) {
            string str = mcs[digits[i]];//将要添加至尾部的字母
            string tmp = ans[0];
            while (tmp.length() == i) {
                for (int j = 0; j < str.length(); j++) {
                    ans.push_back(tmp + str[j]);
                }
                ans.erase(ans.begin());
                tmp = ans[0];
            }
        }
        return ans;
    }
};

 

上一篇:Leetcode/数组/加一


下一篇:力扣