LeetCode每日一题 电话号码 回溯算法

输入法九键，每个按键都代表着不用的字母，我们需要找到不同字影射，来进行不同序列的组成。如下是LeetCode第十七题。

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入：“23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

1. 暴力法
首先还是想到暴力解法，将程序遍历多次，首先要做的事情是建立好字母的字符串的映射，然后将输入的数字字符串串变为数字格式，让每过一个数字时，找到对应的字符串，该字符串中字符放入，再吧其他字符串中的字符放入，这种算法的时间复杂度为O(n3) 具体代码如下：

func letterCombinations(digits string) []string {
	//排除掉特殊情况
	if len(digits) == 0 {
		return nil
	}
	//把对应的字符串输入
	m := []string{ "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	finalout := []string{""}

	for i := 0; i < len(digits); i++ {
	    //把字符串格式改为数字格式，将数字和字符串形成联系
		letters := m[digits[i]-'2']
		length := len(finalout)
		for j := 0; j < length; j++ {
		     //每次将首字符放入，然后改变字符
			tmp := finalout[0]
			finalout = finalout[1:]
			for k := 0; k < len(letters); k++ {
			    //把剩余字符串加上
				finalout = append(finalout, tmp+string(letters[k]))
			}
		}
	}
	return finalout
}

2. 回溯算法
其次就是回溯算法，回溯算法只需要遍历一次，回溯算法在表现上很像递归算法，在本题中的表现比较像宽度优先搜索（BFS），回溯算法和递归算法的根本的不同是，递归算法满足某一条件是，必须返回到上一步，这样不断返回上一步的算法，或者不断调用自己的算法，就是递归，即 F(n) = n*F(n-a), 而回溯算法就是搜索完这条路径上所有的可能，然后返回到出发点，重新搜索。
以例题中的“23”为例，回溯算法的案例是这样的：
对于回溯算法，可以参考以下的代码：

result := [] 类型

func backtrack(路径, 选择列表):
    if (满足结束条件){
        result.add(路径)
        return
        }

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

然后在继续列举，然后组成数组，当数组看全部被组成以后，开始另外一边的搜索：

以下是参考代码：

func letterCombinations(digits string) []string {
    if len(digits)==0 {
        return nil
    }

    m := []string{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}
    finalout := make([]string,0)
    backtrack(digits,0,"",m ,&finalout)
    return finalout
}

func backtrack(digits string,index int,comb string ,m []string,finalout *[]string){
    if index >= len(digits){
        *finalout = append(*finalout,combine)
        return 
    }
    m := m[digits[index] - '2']
    for _,v := range m {
        comb += string(v)
        backtrack(digits,index+1,comb,m,finalout)
        comb = comb[:len(comb)-1]
    }
}