【medium】17. Letter Combinations of a Phone Number 数字组合（数字组合英文）

25-04-22 3

如果您想了解【medium】17.LetterCombinationsofaPhoneNumber数字组合的相关知识，那么本文是一篇不可错过的文章，我们将对数字组合英文进行全面详尽的解释，并且为您提供

如果您想了解【medium】17. Letter Combinations of a Phone Number 数字组合的相关知识，那么本文是一篇不可错过的文章，我们将对数字组合英文进行全面详尽的解释，并且为您提供关于17. Letter Combinations of a Phone Number、17. Letter Combinations of a Phone Number(bfs)、17. Letter Combinations of a Phone Number（电话号码的字母组合）、77. Combinations - Medium的有价值的信息。

本文目录一览：

【medium】17. Letter Combinations of a Phone Number 数字组合（数字组合英文）
17. Letter Combinations of a Phone Number
17. Letter Combinations of a Phone Number(bfs)
17. Letter Combinations of a Phone Number（电话号码的字母组合）
77. Combinations - Medium

【medium】17. Letter Combinations of a Phone Number 数字组合（数字组合英文）

class Solution {
public:
    vector<string> ans; // answers
    
    // dfs实现
    void dfs (int x,int l,string str,string digits,char phone[][4]){
        if (x==l){
            ans.push_back(str);
            return;
        }
        int num = digits[x] - ‘0‘;
        for (int i=0;i<4;i++){
            if (phone[num][i]){
                dfs(x+1,l,str+phone[num][i],digits,phone);
            }
        }
    }
    
    vector<string> letterCombinations(string digits) {
        char phone[10][4] = {{" "},{},{‘a‘,‘b‘,‘c‘},{‘d‘,‘e‘,‘f‘},{‘g‘,‘h‘,‘i‘},{‘j‘,‘k‘,‘l‘},{‘m‘,‘n‘,‘o‘},{‘p‘,‘q‘,‘r‘,‘s‘},{‘t‘,‘u‘,‘v‘},{‘w‘,‘x‘,‘y‘,‘z‘}};
        
        if (digits.length() == 0)
            return ans;
        
        // dfs算法！
        dfs(0,digits.length(),"",phone);
            
        return ans;
        
    }
};

给一个不包含‘0‘和‘1‘的数字字符串，每个数字代表一个字母，请返回其所有可能的字母组合。

下图的手机按键图，就表示了每个数字可以代表的字母。

1	2 ABC	3 DEF
4 GHI	5 JKL	6 MNO
7 PQRS	8 TUV	9WXYZ

17. Letter Combinations of a Phone Number

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"].

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<String>();
        if(digits == null || digits.length() == 0){
            return result;
        }
        Map<Character, char[]> map = new HashMap<Character, char[]>();
        map.put(''2'', new char[]{''a'', ''b'', ''c''});
        map.put(''3'', new char[]{''d'', ''e'', ''f''});
        map.put(''4'', new char[]{''g'', ''h'', ''i''});
        map.put(''5'', new char[]{''j'', ''k'', ''l''});
        map.put(''6'', new char[]{''m'', ''n'', ''o''});
        map.put(''7'', new char[]{''p'', ''q'', ''r'', ''s''});
        map.put(''8'', new char[]{''t'', ''u'', ''v''});
        map.put(''9'', new char[]{''w'', ''x'', ''y'', ''z''});
        StringBuilder sb = new StringBuilder();
        dfs(digits, sb, map, result);
        return result;
    }
    
    public void dfs(String digits, StringBuilder sb, Map<Character, char[]> map, List<String> result){
    	if(sb.length() == digits.length()){
    		result.add(sb.toString());
    		return;
    	}
    	for(char c : map.get(digits.charAt(sb.length()))){ //利用sb.length()查到当前到了第几位
    		sb.append(c);
    		dfs(digits, sb, map, result);
    		sb.deleteCharAt(sb.length() - 1);
    	}
    }
}

17. Letter Combinations of a Phone Number(bfs)

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.

 1 class Solution {
 2     public List<String> letterCombinations(String digits) {
 3         LinkedList<String> res = new LinkedList<String>();
 4         if(digits.isEmpty()) return res;
 5         String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
 6         res.add("");
 7         for(int i=0;i<digits.length();i++){
 8             int x=Character.getNumericValue(digits.charAt(i));
 9             while(res.peek().length()==i){
10                 String t = res.remove();
11                 for (char s :mapping[x].toCharArray())
12                     res.add(t+s);
13             }
14         }
15         return res;
16     }
17 }

17. Letter Combinations of a Phone Number（电话号码的字母组合）

Medium

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.

方法一：递归

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result=new ArrayList<String>();  //存结果
        String[] map={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        char[]tmp=new char[digits.length()];
        if(digits.length()<1)
            return result;
        rec(digits,0,tmp,map,result);
        return result;
    }

    private void rec(String digits,int index,char[] tmp,String[] map,List<String> result) {
        if(index==digits.length()){
            result.add(new String(tmp));
            return;
        }
        char tmpChar=digits.charat(index);
        for(int i=0;i< map[tmpChar - ‘0‘].length();i++){
            tmp[index]=map[tmpChar-‘0‘].charat(i);
            rec(digits,index+1,result);
        }
    }

}

方法二：回溯

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result=new ArrayList<String>();  //存结果
        String[] map={"","wxyz"};
        StringBuilder tmp=new StringBuilder();
        if(digits.length()<1)
            return result;
        backtrack(digits,result);
        return result;
    }

    private void backtrack(String digits,StringBuilder tmp,List<String> result) {
        if(index==digits.length()){
            result.add(new String(tmp));
            return;
        }
        char tmpChar=digits.charat(index);
        for(int i=0;i< map[tmpChar - ‘0‘].length();i++){
            tmp.append(map[tmpChar-‘0‘].charat(i));
            backtrack(digits,result);
            tmp.deleteCharat(tmp.length()-1);
        }
    }

}

总结：

递归是一种数据结构，是函数中调用本身来解决问题。

回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，意思就是对已经知道错误的结果没必要再枚举接下来的答案了。

回溯搜索是深度优先搜索（DFS）的一种。对于某一个搜索树来说（搜索树是起记录路径和状态判断的作用），回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。

77. Combinations - Medium

Given two integers n and k,return all possible combinations of knumbers out of 1 ... n.

Example:

Input: n = 4,k = 2
Output:
[
  [2,4],[3,[2,3],[1,2],]

use DFS (backtracking)

time = O(k * C(n,k)),space = O( C(n,k) )

class Solution {
    public List<List<Integer>> combine(int n,int k) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(n,k,1,new ArrayList<>(),res);
        return res;
    }
    
    public void dfs(int n,int k,int start,List<Integer> list,List<List<Integer>> res) {
        if(list.size() == k) {
            res.add(new ArrayList<>(list));
            return;
        }
        
        for(int i = start; i <= n; i++) {
            list.add(i);
            dfs(n,i + 1,list,res);
            list.remove(list.size() - 1);
        }
    }
}

今天关于【medium】17. Letter Combinations of a Phone Number 数字组合和数字组合英文的介绍到此结束，谢谢您的阅读，有关17. Letter Combinations of a Phone Number、17. Letter Combinations of a Phone Number(bfs)、17. Letter Combinations of a Phone Number（电话号码的字母组合）、77. Combinations - Medium等更多相关知识的信息可以在本站进行查询。

本文标签：