LeetCode - 17. Letter Combinations of a Phone Number

简介: 17. Letter Combinations of a Phone Number Problem's Link  ---------------------------------------------------------------------------- Mean:  给你一个数字串,输出其在手机九宫格键盘上的所有可能组合.

 17. Letter Combinations of a Phone Number

Problem's Link

 ----------------------------------------------------------------------------

Mean: 

给你一个数字串,输出其在手机九宫格键盘上的所有可能组合.

analyse:

使用进位思想来枚举所有组合即可.

Time complexity: O(N)

 

view code

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-02-17-09.57
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);

class Solution
{
public :
    map < char , string > mp;
    vector < string > letterCombinations( string digits)
    {
        mp [ '0' ] = string( " ");
        mp [ '1' ] = string( "");
        mp [ '2' ] = string( "abc");
        mp [ '3' ] = string( "def");
        mp [ '4' ] = string( "ghi");
        mp [ '5' ] = string( "jkl");
        mp [ '6' ] = string( "mno");
        mp [ '7' ] = string( "pqrs");
        mp [ '8' ] = string( "tuv");
        mp [ '9' ] = string( "wxyz");

        vector < int > cntBase;
        vector < string > res;
        int len = digits . length();
        if( len <= 0) return res;
        for( int i = 0; i < len; ++ i)
            cntBase . push_back( 0);
       
        string tmp;
        while( cntBase [ 0 ] < mp [ digits . at( 0 )]. length())
        {
            tmp . clear();
            for( int i = 0; i < len; ++ i)
            {
                tmp . push_back( mp [ digits . at( i )][ cntBase [ i ]]);
            }
            res . push_back( tmp);
            cntBase [ len - 1 ] ++;
            // check and carry
            int carry = 0;
            for( int i = len - 1; i > 0; -- i)
            {
                cntBase [ i ] += carry;
                carry = cntBase [ i ] / ( mp [ digits . at( i )]. length());
                cntBase [ i ] %=( mp [ digits . at( i )]. length());
            }
            cntBase [ 0 ] += carry;
        }
        return res;
    }
};
int main()
{
    Solution solution;
    string s;
    while( cin >>s)
    {
        auto ve = solution . letterCombinations(s);
        for( auto p: ve)
            cout <<p << endl;
    }
    return 0;
}
/*

*/
目录
相关文章
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
105 1
|
6月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
7月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
54 0
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
42 0
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode 136. 只出现一次的数字 Single Number
LeetCode 136. 只出现一次的数字 Single Number
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates
|
人工智能 算法
LeetCode 1347. 制造字母异位词的最小步骤数 Minimum Number of Steps to Make Two Strings Anagram
LeetCode 1347. 制造字母异位词的最小步骤数 Minimum Number of Steps to Make Two Strings Anagram
LeetCode 1342. 将数字变成 0 的操作次数 Number of Steps to Reduce a Number to Zero
LeetCode 1342. 将数字变成 0 的操作次数 Number of Steps to Reduce a Number to Zero