电话号码

[编程题]电话号码

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

九键输入法中 2~9 每个数字对应了若干个的字母，请找出给定数字组合对应的全部字母组合。

数据范围：数字长度 $1 \le n \le 5 \$ ，数字中保证不出现 $0$ 和 $1 \$

键盘数字对应的映射如下：

示例1

输入

"55"

输出

["jj","jk","jl","kj","kk","kl","lj","lk","ll"]

示例2

输入

"3"

输出

["d","e","f"]

算法知识视频讲解

C++

牛娃牛娃

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串vector
     */
    const string lettermap[10]={
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };
    vector<string> res;
    string s;
    //按两个数字 index 应该也为2
    void backtracking(const string &num,int index){
        if(index ==num.size()){
            res.push_back(s);
            return ;
        }
        int digit =num[index]-'0';
        string letters= lettermap[digit];
        for(int i=0;i<letters.size();i++){
            s.push_back(letters[i]);
            backtracking(num,index+1);
            s.pop_back();
        }
    }
    vector<string> phoneNumber(string num) {
        // write code here
        s.clear();
        res.clear();
        if(num.size()==0)return res;
        backtracking(num,0);
        return res;
    }
};

发表于 2022-03-17 12:14:17 回复(0)

牛暴发

说真的这测试用例准备的真不怎么滴，大小写不一样就不通过，一会大写，一会小写

发表于 2022-11-09 15:41:37 回复(0)

Ricky048

测试用例跟题目给出的不一样，统一一下吧，测试用例需要小写但是题目给的以及默认测试用例是大写的

发表于 2023-05-07 13:06:38 回复(0)

小谷围做题家

package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param num string字符串 
 * @return string字符串一维数组
*/
func phoneNumber( num string ) []string {
    n2c:=map[byte]string{
        '2':"abc",
        '3':"def",
        '4':"ghi",
        '5':"jkl",
        '6':"mno",
        '7':"pqrs",
        '8':"tuv",
        '9':"wxyz",
    }
    ans:=[]string{}
    var dfs func(string,int)
    dfs=func(s string,idx int){
        if idx==len(num){
            ans=append(ans,s)
            return
        }
        for _,ch:=range []byte(n2c[num[idx]]){
            s+=string(ch)
            dfs(s,idx+1)
            s=s[:len(s)-1]
        }
    }
    dfs("",0)
    return ans
}

发表于 2023-03-28 21:42:07 回复(0)

凡书尘

题目有问题吧，用例输入‘6’，预期输出里的MNO全是小写，但是题目里的是大写

发表于 2023-03-19 15:12:57 回复(0)

Java

FARO_Z

经典回溯题

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串ArrayList
     */
    private static final String[] seq = new String[]{
            "",
            "",
            "ABC",
            "DEF",
            "GHI",
            "JKL",
            "MNO",
            "PQRS",
            "TUV",
            "WXYZ"};

    public ArrayList<String> phoneNumber (String num) {
        ArrayList<String> res = new ArrayList<>();
        StringBuilder track = new StringBuilder();
        int depth = num.length();
        backtrack(track,res,0,depth,num);
        return res;
    }

    private void backtrack(StringBuilder track,ArrayList<String>res,int currDepth,int maxDepth,String num) {
        if (currDepth>=maxDepth) {
            res.add(track.toString());
            return;
        }
        int index = (int) num.charAt(currDepth) - '0';
        String currSeq = seq[index];
        for (int i = 0; i < currSeq.length(); i++) {
            track.append(currSeq.charAt(i));
            backtrack(track,res,currDepth+1,maxDepth,num);
            track.deleteCharAt(track.length()-1);
        }
    }
}

发表于 2022-07-12 17:52:35 回复(0)

啊哈哈h

import java.util.*;
public class Solution {
    String[] letter_map = {" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> phoneNumber (String digits) {
		if(digits == null || digits.length() == 0)
            return new ArrayList<>();
        dfs(digits, 0, new StringBuilder());  
        return res;  
	}
	void dfs(String digits, int index, StringBuilder sb) {
        if(digits.length() == index){
            res.add(sb.toString());
            return;
        }
	    char c = digits.charAt(index);
        int digit = c - '0';
        String string = letter_map[digit];
        for(int i = 0; i < string.length(); i++){
            sb.append(string.charAt(i));
            dfs(digits, index + 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

发表于 2022-03-27 17:28:30 回复(0)