电话字母的组合

[编程题]电话字母的组合

热度指数：9375 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个仅包含数字的字符串，给出所有可能的字母组合。

数字到字母的映射方式如下:(就像电话上数字和字母的映射一样)

Input:Digit string "23"Output:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

注意：虽然上述答案是按字典序排列的，但你的答案可以按任意的顺序给出

示例1

输入

"23"

输出

["ad","ae","af","bd","be","bf","cd","ce","cf"]

算法知识视频讲解

Java

kkk大人

使用回溯法

    ArrayList<String> res =new ArrayList<String>();
    String[] map={"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public ArrayList<String> letterCombinations (String digits) {
        // write code here
        int size = digits.length();
        if(size<=0)
        {
            res.add(digits);
            return res;
        }
          
        StringBuffer sb= new StringBuffer();
        helper(digits,0,sb);
        return res;
    }
    
    void helper(String digits,int index,StringBuffer sb)
    {
        if(index>=digits.length())
        {
            res.add(sb.toString());
            return;
        }
        
        int s = (int)digits.charAt(index)-'0';
        for(int i=0;i<map[s].length();i++)
        {
            sb.append(map[s].charAt(i));
            helper(digits,index+1,sb);
            sb=sb.deleteCharAt(sb.length()-1);
        }
    }

发表于 2020-07-31 18:42:09 回复(0)

Java

zhguixin

Java版本的回溯解法。

    public ArrayList<String> letterCombinations (String digits) {
        // write code here
        traceBack(new StringBuffer(), 0, digits);
        return res;
    }


    // index为输入的数字字符串中的第几个数字
    private void traceBack(StringBuffer str, int index, String digits) {
        if (index == digits.length()) {
            res.add(str.toString());
            return;
        }
        char[] charArray = digits.toCharArray();
        // 目前回溯到第几个数字
        int num = Character.getNumericValue(charArray[index]);
        // 取出数字对应的字符串
        String item = mapping[num];
        for (char ch : item.toCharArray()) {
            str.append(ch);
            traceBack(str, index + 1, digits);
            str.deleteCharAt(str.length() - 1);
        }
    }

发表于 2020-07-20 20:17:22 回复(0)

Java

HW柯可

import java.util.HashMap;
import java.util.ArrayList;

public class Solution {
    ArrayList<String> res = new ArrayList<>();
    String temp = "";
    public ArrayList<String> letterCombinations(String digits) {
        if(digits.length() == 0 || digits == null){
            res.add("");
            return res;
        }       
    HashMap<Character,String> map=new HashMap<>();
    map.put('0',""); map.put('1',"");map.put('2',"abc");
    map.put('3',"def");map.put('4',"ghi");map.put('5',"jkl");
    map.put('6',"mno"); map.put('7',"pqrs");map.put('8',"tuv");
    map.put('9',"wxyz");
    res = combine(digits, 0, map);
    return res;
    }
    //回溯法
    public ArrayList<String> combine(String digits, int start, HashMap<Character,String> map){
        if(start == digits.length()){
            res.add(temp);
            return res;
        }
        String str = map.get(digits.charAt(start));
        for(int i = 0; i < str.length(); i++){
            temp = temp + str.charAt(i);
            combine(digits, start + 1, map);
            temp = temp.substring(0, temp.length() - 1);
        }
        return res;
    }
}

发表于 2019-07-10 18:34:47 回复(0)

Java

PG.13

import java.util.*;
//回溯法
public class Solution {
ArrayList<String>res = new ArrayList<String>();
public ArrayList<String> letterCombinations(String digits) {
if(digits==null||digits.length()==0){
res.add("");
return res;
}
String[] mapping = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
int index = 0;
String result = "";
backTrace(index,result,digits,mapping);
return res;
}
public void backTrace(int index,String result,String digits,String[] mapping){
    if(result.length()>=digits.length()){
        res.add(result);
        return;
    }
    String str = mapping[Integer.parseInt(String.valueOf(digits.charAt(index)))-2];
    for(char c:str.toCharArray()){
        result+=c;
        backTrace(index+1,result,digits,mapping);
        result = result.substring(0,result.length()-1);
    }
}
}

发表于 2017-10-26 11:38:54 回复(0)

Java

Holiday_12138

import java.util.*;
public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<String>();
        HashMap<Character,char[]> map = new HashMap<Character,char[]>();
        map.put('0',new 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'});
        getString(digits, 0, res, "", map);
        return res;
    }
    public void getString(String digits, int i, ArrayList<String> res, String str, HashMap<Character,char[]> map) {
        if(i < digits.length()) {
            if(map.containsKey(digits.charAt(i)))
                for(char c : map.get(digits.charAt(i))) {
					String tmp=str+c;
                    getString(digits, i+1, res, tmp, map);
                }
        }
        else {
            res.add(str);
        }
    }
}

发表于 2017-06-02 13:55:17 回复(0)

Java

城市里的养猫者

   public List<String> letterCombinations(String digits) {
    LinkedList<
    LinkedList<String> ans = new LinkedList<String>();
    
    String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    ans.add(
    ans.add("");
    
    for(int i =0; i<digits.length();i++){
        
        int x = Character.getNumericValue(digits.charAt(i));
        
        while(ans.peek().length()==i){
            
            String t = ans.remove();
            
            for(char s : mapping[x].toCharArray())
                ans.add(t+s);
        }
    }
    
                ans.add(t+s);
        }
    }
    return ans;
}
}

发表于 2017-03-12 23:42:52 回复(0)