C++实现LeetCode(17.电话号码的字母组合)

[LeetCode] 17. Letter Combinations of a Phone Number 电话号码的字母组合

Given a string containing digits from 2-9inclusive, 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.

这道题让我们求电话号码的字母组合，即数字2到9中每个数字可以代表若干个字母，然后给一串数字，求出所有可能的组合。这里可以用递归 Recursion 来解，需要建立一个字典，用来保存每个数字所代表的字符串，然后还需要一个变量 level，记录当前生成的字符串的字符个数，实现套路和上述那些题十分类似。在递归函数中首先判断 level，如果跟 digits 中数字的个数相等了，将当前的组合加入结果 res 中，然后返回。我们通过 digits 中的数字到 dict 中取出字符串，然后遍历这个取出的字符串，将每个字符都加到当前的组合后面，并调用递归函数即可，参见代码如下：

解法一：

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> res;
        vector<string> dict{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        letterCombinationsDFS(digits, dict, 0, "", res);
        return res;
    }
    void letterCombinationsDFS(string& digits, vector<string>& dict, int level, string out, vector<string>& res) {
        if (level == digits.size()) {res.push_back(out); return;}
        string str = dict[digits[level] - '0'];
        for (int i = 0; i < str.size(); ++i) {
            letterCombinationsDFS(digits, dict, level + 1, out + str[i], res);
        }
    }
};

这道题也可以用迭代 Iterative 来解，在遍历 digits 中所有的数字时，先建立一个临时的字符串数组t，然后跟上面解法的操作一样，通过数字到 dict 中取出字符串 str，然后遍历取出字符串中的所有字符，再遍历当前结果 res 中的每一个字符串，将字符加到后面，并加入到临时字符串数组t中。取出的字符串 str 遍历完成后，将临时字符串数组赋值给结果 res，具体实现参见代码如下：

解法二：

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> res{""};
        vector<string> dict{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        for (int i = 0; i < digits.size(); ++i) {
            vector<string> t;
            string str = dict[digits[i] - '0'];
            for (int j = 0; j < str.size(); ++j) {
                for (string s : res) t.push_back(s + str[j]);
            }
            res = t;
        }
        return res;
    }
};

到此这篇关于C++实现LeetCode(17.电话号码的字母组合)的文章就介绍到这了,更多相关C++实现电话号码的字母组合内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(769.可排序的最大块数)

    [LeetCode] 769.Max Chunks To Make Sorted 可排序的最大块数 Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of "chunks" (partitions), and individually sort each chunk.  After concatenating them,

  • C++实现LeetCode(13.罗马数字转化成整数)

    [LeetCode] 13. Roman to Integer 罗马数字转化成整数 Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol       Value I                  1 V                 5 X                10 L                 50 C                100 D 

  • C++实现LeetCode(16.最近三数之和)

    [LeetCode] 16. 3Sum Closest 最近三数之和 Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly on

  • C++实现LeetCode(12.整数转化成罗马数字)

    [LeetCode] 12. Integer to Roman 整数转化成罗马数字 Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol       Value I                   1 V                  5 X                 10 L                  50 C                100

  • C++实现LeetCode(45.跳跃游戏之二)

    [LeetCode] 45. Jump Game II 跳跃游戏之二 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last i

  • C++实现LeetCode(14.最长共同前缀)

    [LeetCode] 14. Longest Common Prefix 最长共同前缀 Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Example 1: Input: ["flower","flow",&q

  • C++实现LeetCode(768.可排序的最大块数之二)

    [LeetCode] 768.Max Chunks To Make Sorted II 可排序的最大块数之二 This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements cou

  • C++实现LeetCode(17.电话号码的字母组合)

    [LeetCode] 17. Letter Combinations of a Phone Number 电话号码的字母组合 Given a string containing digits from 2-9inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone butt

  • JS实现电话号码的字母组合算法示例

    JS实现电话号码的字母组合算法示例

    本文实例讲述了JS实现电话号码的字母组合算法.分享给大家供大家参考,具体如下: 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合. 给出数字到字母的映射如下(与电话按键相同).注意 1 不对应任何字母. 示例: 输入:"23" 输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "c

  • C++ 电话号码的字母组合功能实现

    C++ 电话号码的字母组合功能实现

    目录 电话号码的字母组合 描述 示例1 示例2 示例3 思路/解法 方式一 方式二 电话号码的字母组合 描述 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合.答案可以按 任意顺序 返回. 给出数字到字母的映射如下(与电话按键相同).注意 1 不对应任何字母. 示例1 输入:digits = "23"输出:["ad","ae","af","bd","be","b

  • python实现信号时域统计特征提取代码

    1.实验数据需求 为了对采集的压力实验数据做特征工程,需要对信号进行时域的统计特征提取,包含了均值.均方根.偏度.峭度.波形因子.波峰因子.脉冲因子.峭度因子等,现用python对其进行实现. 2.python实现 其中的输入参数含义: ① data:实验数据的DataFrame ② p1:所截取实验信号的起始采样点位置 ③ p2:所截取实验信号的终止采样点位置 from pandas import Series import math pstf_list=[] def psfeatureTim

  • C++回溯算法深度优先搜索举例分析

    C++回溯算法深度优先搜索举例分析

    目录 扑克牌全排列 员工的重要性 图像渲染 被围绕的区域 岛屿数量 电话号码的字母组合 组合总数 活字印书 N皇后 扑克牌全排列 假如有编号为1~ 3的3张扑克牌和编号为1~3的3个盒子,现在需要将3张牌分别放到3个盒子中去,且每个盒子只能放一张牌,一共有多少种不同的放法. 解题思路:假定按照牌面值从小到大依次尝试,即将1号牌放入第一个盒子中.按此顺序继续向后走,放完第三个盒子时,手中的牌也已经用完,再继续往后则到了盒子的尽头.此时一种放法已经完成了,即这条路走到了尽头,需要折返,重新回到上一个

  • Pipes实现LeetCode(193.验证电话号码)

    [LeetCode] 193.Valid Phone Numbers 验证电话号码 Given a text file file.txt that contains list of phone numbers (one per line), write a one liner bash script to print all valid phone numbers. You may assume that a valid phone number must appear in one of th

  • jquery validation验证身份证号,护照,电话号码,email(实例代码)

    validata.htm 复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http

  • jQuery电话号码验证实例

    本文实例为大家分享了jQuery电话号码验证的具体代码,供大家参考,具体内容如下 电话号码验证: //移动号码归属地支持号段:134 135 136 137 138 139 147 150 151 152 157 158 159 178 182 183 184 187 188 //联通号码归属地支持号段:130 131 132 145 155 156 176 186 //电信号码归属地支持号段:133 153 177 180 181 189 //移动运营商:170 移动: 2G号段(GSM):1

  • vscode中配置LeetCode插件的教程(愉快刷题)

    大家好,今早在B站看到up主的vscode里藏了leetcode插件,这才知道原来还有这款神器.但是没想到在用的时候遇到了一些麻烦,花了一点时间才解决.所以写这篇文章除了给大家安利这个好用的插件之外,也是为了帮助更多的同学避免踩坑. 简介vscode vscode在工业界鼎鼎大名,被誉为微软少有的拿得出手的精品(逃).原本是不想过多赘述的,但是鉴于许多粉丝还是正在上学的萌新,所以花点笔墨简单介绍一下. vscode是微软开发的编辑器,严格说起来它并不是一个IDE,只是一个编辑器.但是由于它支持嵌

  • 如何用C++制作LeetCode刷题小技巧-错题记录本

    一 . 刷题小技巧 1,c++中的for(auto a:b)用法 for(auto a:b)中b为一个容器,效果是利用a遍历并获得b容器中的每一个值,但是a无法影响到b容器中的元素. for(auto &a:b)中加了引用符号,可以对容器中的内容进行赋值,即可通过对a赋值来做到容器b的内容填充. 2,c++中map的元素进行按照值排序(默认按照键排序) 为什么不能对map进行按值排序呢?因为sort排序只能对线性结构进行排序,而map是采用红黑树的数据结构. 一是通过将map转换到序列容器,再用

随机推荐