题目

leetcode:17

代码与解析

要存储数字和字母对应关系的话,可以用数组或者map
这里采用数组。
前面之所以加两个空,因为函数参数的digits是从2~9,为了对应上索引。采用map的话就不用了。

digitsMap := [10]string{
    "",     // 0
    "",     // 1
    "abc",  // 2
    "def",  // 3
    "ghi",  // 4
    "jkl",  // 5
    "mno",  // 6
    "pqrs", // 7
    "tuv",  // 8
    "wxyz", // 9
}


回溯三部曲:

  • 确定参数及返回值
    传入tempStringIndex,来记录遍历第几个数字

  • 确定终止条件
    tempString长度等于digits的时候,说明长度符合要求,要添加进res

  • 确定单层逻辑
    tempInputInt := digits[Index]-'0' // 转为int
    用这句话转为int, 输入的digits是:类似“234”这种,如果不用这种方式,tempInputInt接受到的则是ascii

// 获取“2345”中的 第Index个元素,得到类似2,3,4,5
tempInputInt := digits[Index]-'0' // 转为int
// 从数组对应关系取值,可以用map
tempS := digitsMap[tempInputInt]

tmp就是这样的一个字符串,
for横向遍历字符串,取到具体一个字母
递归取i+i个,这样深度,广度都有了

func letterCombinations(digits string) []string {
    res := []string{}
    if len(digits)==0{
        return res
    }
    digitsMap := [10]string{
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz", // 9
    }

    var backtracking func(tempString string, Index int)
    backtracking = func(tempString string, Index int){
        if len(tempString)==len(digits){
            res = append(res, tempString)
            return
        }
        // 获取“2345”中的 第Index个元素,得到类似2,3,4,5
        tempInputInt := digits[Index]-'0' // 转为int
        // 从数组对应关系取值,可以用map
        tempS := digitsMap[tempInputInt]
        for i:=0;i<len(tempS);i++{
            tempString = tempString + string(tempS[i])
            backtracking(tempString, Index+1)
            tempString = tempString[:len(tempString)-1]
        }
    }
    backtracking("", 0)
    return res
}
分类: 算法

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:190 个
  • 运行天数:975 天
  • 访问总数:72638 人次

浙公网安备33011302000604

辽ICP备20003309号