LeetCode 17. Letter Combinations of a Phone Number

最近在做LeetCode中的题，第一次更C++和算法系列文章就拿这道题开张吧。

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.

首先看到这道题，感觉无从下手，我也是这种心理，怎么下手呀，喜欢百度，好吧原谅我做的题少，找了几个版本，找到这一版的，感觉讲解的非常清晰。

参考：

枚举所有情况：

对每一个输入数字，对于已有的排列中的每一个字符串，分别加入该数字所代表的每一个字符。

到这里想到了什么，对三重for循环。

举例：

初始化排列{""} //空的容器

1、输入 2 ；

此时已有的排列是 “” 空的字符串，得到{“a”,“b”,“c”}

2、输入3；

遍历已有的排列中的每一个字符串，则：

1>对于"a", 删除"a",加入’d’，‘e’，‘f’，得到{“b”,“c”,“ad”,“ae”,“af”}

2>对于"b",删除"b",加入’d’ ，‘e’， ‘f’，得到{“c” , “ad” ,“ae” ,“af” ,“bd”, “be”, “bf”}

3>同理删除 “c”, 加入’d’， ‘e’， ‘f’ ,得到 {“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”}

注意：

1.每次添加新字母时，应该先取vector变量ret的size(),遍历此大小即可，因为ret vertor变量是变化的。

2.删除vector首元素代码为：

ret.erase(ret.begin());

介于c++解决此类算法题最常用的就是vector和string对象。后面我会专门开辟系列文章学习这两个对象。

class Solution {public:	vector
   
     letterCombinations(string digits){		vector
    
      ret;		if(digits == "")		{			return ret;		}		ret.push_back("");      //初始化 {""}		vector
     
       dict(10);   //初始化大小为10的词典  0--9		dict[2] = "abc";		dict[3] = "def";		dict[4] = "ghi";		dict[5] = "jkl";		dict[6] = "mno";		dict[7] = "pqrs";		dict[8] = "tuv";		dict[9] = "wxyz";				for(int i = 0; i < digits.size(); i++)		{			int size = ret.size();			for(int j = 0; j < size; j++)			{				string cur = ret[0];				ret.erase(ret.begin());				for(int k = 0; k < dict[digits[i] - '0'].size(); k++)				{					ret.push_back(cur + dict[digits[i] - '0'][k]);				}			}		}		return ret;	}};

转载地址：http://dkzjn.baihongyu.com/

你可能感兴趣的文章