Leetcode 17 Letter Combinations of a Phone Number

triplebee

发布于 2018-01-12 15:10:31

4990

发布于 2018-01-12 15:10:31

文章被收录于专栏：计算机视觉与深度学习基础计算机视觉与深度学习基础

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.

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.

题意为输出所有按键可能表示的字母组合。

因为不知道按键组合有多长，所以可以用搜索来做，

为了效率我用的是BFS，不过好像也没快到哪里去。

先打印出字典表，用队列进行搜索，算法的复杂度最优就行了，不必在意常数项的问题。

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        string dic[11]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        vector<string> result;
        queue <string> q;
        q.push("");
        for(int i=0;i<digits.length();i++)
        {
            int cnt=q.size();
            while(cnt--)
            {
                string temp=q.front();
                q.pop();
                for(int j=0;j<dic[digits[i]-'0'].length();j++)
                    q.push(temp+dic[digits[i]-'0'][j]);
            }
        }
        if(q.front()=="") q.pop();
        while(!q.empty())
        {
            result.push_back(q.front());
            q.pop();
        }
        return result;
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-08-29 ，如有侵权请联系 cloudcommunity@tencent.com 删除

combinations