17. Letter Combinations of a Pho

题目

. 给定一个包含 2-9 数字的字符串，以任意顺序返回所有可能的字母组合。 2-9 代表的字母和电话号码相同。

解析

问题看起来很简单，组合遍历即可，但问题在于，因为字符串长度不固定，所以循环次数不固定。用递归可以解决。

1. 递归函数接受一个字符串和一个数字，返回这个字符串和数字组成的所有字符。
2. 为了保证递归，递归函数应当知道自己当前是第几个字符，下一个是什么字符。

伪代码

phone := [10][]str{{},{},{a,b,c},{d,e,f}}

fetch(str, num) []string
  if num == end
      return nil
  var rsts []string
   for i<len(phone[num])
        strs.append(fetch(str+phone[num][i], lastnum)
  return rsts

代码

func letterCombinations(digits string) []string {
    phone := [][]string{
        {},
        {},
        {"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 len(digits) == 0 {
        return nil
    }
    
    return fetch("",0, digits, phone)
}

func fetch(str string, idx int, digits string, phone [][]string) []string {
    var rst []string
    if idx == len(digits) {
        return []string{str}
    }
    for i:=0; i<len(phone[digits[idx]-'0']); i++ {
        strs := fetch(str+phone[digits[idx]-'0'][i], idx+1, digits, phone)
        rst=append(rst, strs...)
    }
    return rst
}