leetcode 17. Letter Combinations of a Phone Number 按照indexDFS深度优先遍历

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.

题意很简单，就是寻找所有的可能的组成，这是一个组合计算的问题。如何计算呢？可以递归去计算，这个类似寻找组合数，还可以直接迭代计算。思想就很简单了，就不说了，直接上代码。

代码如下：

import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class Solution { Map<Character,char[]> map=new HashMap<Character,char[]>(); public void init() { char []a={'a','b','c'}; map.put('2',a); char []d={'d','e','f'}; map.put('3',d); char []g={'g','h','i'}; map.put('4',g); char []j={'j','k','l'}; map.put('5',j); char []m={'m','n','o'}; map.put('6',m); char []p={'p','q','r','s'}; map.put('7',p); char []t={'t','u','v'}; map.put('8',t); char []w={'w','x','y','z'}; map.put('9',w); } public List<String> letterCombinations(String digits) { List<String> res=new ArrayList<>(); if(digits==null || digits.equals("")) return res; init(); getAll(res,"",0,digits); return res; } /* * 递归计算 * */ private void getAll(List<String> res, String one, int k, String digits) { if(k==digits.length()) { res.add(new String(one)); return ; }else { char[] b=map.get(digits.charAt(k)); for(int i=0;i<b.length;i++) getAll(res, one+b[i], k+1, digits); } } /* * 迭代计算 * */ public List<String> letterCombinations111(String digits) { List<String> res=new ArrayList<>(); if(digits==null || digits.equals("")) return res; init(); int len=digits.length(); if(len==1) { char []p=map.get(digits.charAt(0)); for(int i=0;i<p.length;i++) { res.add(""+p[i]); } }else { List<String> tmp=new ArrayList<>(); char []p=map.get(digits.charAt(0)); for(int i=0;i<p.length;i++) { tmp.add(""+p[i]); } for(int i=1;i<len;i++) { int tmpLen=tmp.size(); char []now=map.get(digits.charAt(i)); for(int j=0;j<tmpLen;j++) { for(int k=0;k<now.length;k++) { String gg=tmp.get(j)+""+now[k]; tmp.add(gg); } } int cc=tmpLen-1; while(cc>=0) { tmp.remove(cc); cc--; } } res.addAll(tmp); } return res; } public static void main(String[] args) { Solution solution=new Solution(); System.out.println(solution.letterCombinations("234")); } }

下面是C++的答案，其实这是一道很经典的DFS深度优先遍历的做法的示例。

代码如下:

#include <iostream> #include <vector> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <stack> #include <string> #include <climits> #include <algorithm> #include <sstream> #include <functional> #include <bitset> #include <numeric> #include <cmath> #include <regex> using namespace std; class Solution { public: map<char, string> map1; vector<string> res; vector<string> letterCombinations(string digits) { if (digits.size() <= 0) return res; map1 = { { '2',"abc" },{ '3',"def" },{ '4',"ghi" },{ '5',"jkl" },{ '6',"mno" },{ '7',"pqrs" },{ '8',"tuv" },{ '9',"wxyz" } }; getByDFS(digits, 0, ""); return res; } void getByDFS(string dig, int index, string one) { if (index == dig.length()) { res.push_back(one); return; } else { string aa = map1[dig[index]]; for (int i = 0; i < aa.size(); i++) getByDFS(dig, index + 1, one + aa[i]); } } };