由操作实例已知结果
由输入输出实例，可知遍历路径，该遍历路径也是最好的路径，因此只要依次遍历每个输出字符串即可
以23为例，遍历路径即为："ad","ae","af","bd","be","bf","cd","ce","cf"，两外无顺序要求
要寻找该路径的遍历模型
冒泡式遍历无法实现，因为无法确定输入字母集合个数。但是可以发现如”ad“，实际上是位置{0,1}，”ae“也可以是位置{0,2}，由此可得，遍历路径可以转换为：
{0,1},{0,2},{0,3},{0,4},{1,0}...，至此可以为该路径设计遍历模型，可以使用一个可以获取下一遍历节点的迭代器，该迭代器的next操作类似由{m,n}获取{m,n+1}，当位置超出子母个数时，可以修正该位置
伪代码实现
- 设计位置pos结构体，用于表示{m,n}位置
- 写遍历框架，基本是调用迭代器遍历
- 编写迭代器next函数，基本逻辑为当前位置+1，当位置超出时修正
至此可以写代码调试至作题完毕。
题解暂作记录
package main
import "fmt"
var phoneLettersMap = map[string]string{
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
type Pos struct {
index int
phoneLetters string
}
type PhoneResultIterator struct {
pos []Pos
}
func (phoneResultIterator *PhoneResultIterator) next() *PhoneResultIterator {
phoneResultIterator.pos[0].index++
for i, pos := range phoneResultIterator.pos {
// 若当前位数超出对应子母串位数，修正当前为0，下一位加1
if pos.index > len(pos.phoneLetters)-1 {
// 若修正位数时为最后一位，终止
if i >= len(phoneResultIterator.pos)-1 {
return nil
}
phoneResultIterator.pos[i].index = 0
phoneResultIterator.pos[i+1].index++
}
}
return phoneResultIterator
}
func (phoneResultIterator *PhoneResultIterator) toString() string {
var letterResString string = ""
for _, pos := range phoneResultIterator.pos {
letterResString = letterResString + string(pos.phoneLetters[pos.index])
}
return letterResString
}
func letterCombinations(digits string) []string {
stringRes := make([]string, 0)
if len(digits) <= 0 {
return stringRes
}
// 初始化结果迭代器
phoneResultIterator := &PhoneResultIterator{}
phoneResultIterator.pos = make([]Pos, len(digits))
for i, _ := range phoneResultIterator.pos {
phoneResultIterator.pos[i].index = 0
phoneResultIterator.pos[i].phoneLetters = phoneLettersMap[string(digits[i])]
}
// 遍历结果集
for phoneResultIterator != nil {
stringRes = append(stringRes, phoneResultIterator.toString())
phoneResultIterator = phoneResultIterator.next()
}
return stringRes
}
func main() {
res := letterCombinations("274")
fmt.Print(res)
}
看题解发现对于遍历所有集合有通用解决模型：回溯
回溯专题
后面会做一个回溯的专题训练
回溯基本模型
查阅资料发现回溯有通用的朴素模型：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
回溯经典问题
回溯经典问题包括：
- N皇后回溯
- 01背包
- 树深度优先遍历
- 树广度优先遍历
电话号码子母组合回溯解法
回溯解法
package main
import "fmt"
var phoneLettersMap = map[string][]string{
"2": {"a", "b", "c"},
"3": {"d", "e", "f"},
"4": {"g", "h", "i"},
"5": {"j", "k", "l"},
"6": {"m", "n", "o"},
"7": {"p", "q", "r", "s"},
"8": {"t", "u", "v"},
"9": {"w", "x", "y", "z"},
}
var stringRes []string
var list [][]string
func backTrace(track string, row int) bool {
// 递归基
if row == len(list) {
stringRes = append(stringRes, track)
return true
}
// 遍历列表
for _, letter := range list[row] {
// 选择：得到新track
track := track + letter
// 列表：得到下一级决策组，触发bt调用
backTrace(track, row+1)
// 取消选择track
track = track[0 : len(track)-1]
}
return true
}
func letterCombinations(digits string) []string {
stringRes = make([]string, 0)
list = make([][]string, 0)
// 特殊case
if digits == "" {
return stringRes
}
// 初始化遍历列表
for i := 0; i < len(digits); i++ {
list = append(list, phoneLettersMap[string(digits[i])])
}
// 遍历
backTrace("", 0)
return stringRes
}
func main() {
res := letterCombinations("273")
fmt.Print(res)
}
