0017. Letter Combinations of a Phone Number | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0017.Letter-Combinations-of-a-Phone-Number/

[techkang]

var (
	letterMap = []string{
		" ",
		"",
		"abc",
		"def",
		"ghi",
		"jkl",
		"mno",
		"pqrs",
		"tuv",
		"wxyz",
	}
	res = []string{}
	final = 0
)
func letterCombinations(digits string) []string {
	if digits==""{
		return []string{}
	}
	index := digits[0]-'0'
	letter :=letterMap[index]
	tmp := []string {}
	for i:=0;i<len(letter);i++{
		if len(res)==0{
			res = append(res, "")
		}
		for j:=0;j<len(res);j++{
			tmp = append(tmp, res[j]+string(letter[i]))
		}
	}
	res = tmp
	final++
	letterCombinations(digits[1:])
	final--
	if final==0{
		tmp = res
		res = []string{}
	}
	return tmp
}

这道题也可以不用创建新的递归函数

[halfrost]

var (
	letterMap = []string{
		" ",
		"",
		"abc",
		"def",
		"ghi",
		"jkl",
		"mno",
		"pqrs",
		"tuv",
		"wxyz",
	}
	res = []string{}
	final = 0
)
func letterCombinations(digits string) []string {
	if digits==""{
		return []string{}
	}
	index := digits[0]-'0'
	letter :=letterMap[index]
	tmp := []string {}
	for i:=0;i<len(letter);i++{
		if len(res)==0{
			res = append(res, "")
		}
		for j:=0;j<len(res);j++{
			tmp = append(tmp, res[j]+string(letter[i]))
		}
	}
	res = tmp
	final++
	letterCombinations(digits[1:])
	final--
	if final==0{
		tmp = res
		res = []string{}
	}
	return tmp
}

这道题也可以不用创建新的递归函数

写的挺清晰的，收录了你这个解法了哈~ 谢谢大佬指点👍🏻 @techkang

[hujun2020]

func letterCombinations(digits string) []string { all := map[string][]string{ "2":[]string{"a","b","c"}, "3":[]string{"d","e","f"}, "4":[]string{"g","h","i"}, "5":[]string{"j","k","l"}, "6":[]string{"m","n","o"}, "7":[]string{"p","q","r","s"}, "8":[]string{"t","u","v"}, "9":[]string{"w","x","y","z"}, } res ,tmp:= []string{},[]string{""} for _,v := range digits{ res = combineLetter(tmp,all[string(v)]) tmp = res } return res } func combineLetter(s1,s2 []string) []string { res := []string{} for _,v1 := range s1{ for _,v2 := range s2{ res = append(res,v1+v2) } } return res }

只能暴力解

[hujun2020]

func letterCombinations(digits string) []string {
	all := map[string][]string{
		"2":[]string{"a","b","c"},
		"3":[]string{"d","e","f"},
		"4":[]string{"g","h","i"},
		"5":[]string{"j","k","l"},
		"6":[]string{"m","n","o"},
		"7":[]string{"p","q","r","s"},
		"8":[]string{"t","u","v"},
		"9":[]string{"w","x","y","z"},
	}
	res ,tmp:= []string{},[]string{""}
	for _,v := range digits{
		res = combineLetter(tmp,all[string(v)])
		tmp = res
	}
	return res
}
func combineLetter(s1,s2 []string) []string {
	 res := []string{}
	 for _,v1 := range s1{
		 for _,v2 := range s2{
			res = append(res,v1+v2)
		 }
	 }
	 return res
}
``
暴力暴力

[chiyoi]

python check-in

        if not len(digits):
            return []
        mapping = {
                '2': 'abc',
                '3': 'def',
                '4': 'ghi',
                '5': 'jkl',
                '6': 'mno',
                '7': 'pqrs',
                '8': 'tuv',
                '9': 'wxyz'
                }
        strings = []
        def getLetters(partDigits, string = ''):
            if not len(partDigits):
                strings.append(string)
                return
            for character in mapping[partDigits[0]]:
                getLetters(partDigits[1:], string + character)
        getLetters(digits)
        return strings

60%有点不好意思发，但是感觉没法更快了

[halfrost]

python check-in

        if not len(digits):
            return []
        mapping = {
                '2': 'abc',
                '3': 'def',
                '4': 'ghi',
                '5': 'jkl',
                '6': 'mno',
                '7': 'pqrs',
                '8': 'tuv',
                '9': 'wxyz'
                }
        strings = []
        def getLetters(partDigits, string = ''):
            if not len(partDigits):
                strings.append(string)
                return
            for character in mapping[partDigits[0]]:
                getLetters(partDigits[1:], string + character)
        getLetters(digits)
        return strings

60%有点不好意思发，但是感觉没法更快了

@CHIYOI 60% 确实不太好，你看看 discussion 里面 python 别人的解法，可能哪里有优化方法，你可以学学。💪🏻

[0RAJA]

100%

func letterCombinations(digits string) (ret []string) {
    if digits == ""{
        return
    }
    letterMap := []string{
		" ",    //0
		"",     //1
		"abc",  //2
		"def",  //3
		"ghi",  //4
		"jkl",  //5
		"mno",  //6
		"pqrs", //7
		"tuv",  //8
		"wxyz", //9
	}
    result := make([]byte,len(digits))
    var dfs func(step int)
    dfs = func(step int){
        if step >= len(digits){
            ret = append(ret,string(result))
            return
        }
        for _,v:=range letterMap[digits[step]-'0']{
            result[step] = byte(v)
            dfs(step+1)
        }
    }
    dfs(0)
    return
}

[RTsien]

暴力递归

var letterMap = []string{
    "",
    "",
    "abc",
    "def",
    "ghi",
    "jkl",
    "mno",
    "pqrs",
    "tuv",
    "wxyz",
}

func letterCombinations(digits string) []string {
    res := make([]string, 0)
    if len(digits) == 0 {
        return res
    }
    for _, letter := range letterMap[digits[0] - '0'] {
        res = append(res, string(letter))
    }
    if len(digits) > 1 {
        tails := letterCombinations(digits[1:])
        var tmp []string
        tmp, res = res, tmp
        for _, head := range tmp {
            for _, tail := range tails {
                res = append(res, head + tail)
            }
        }
    }
    return res
}