由操作實例已知結(jié)果
由輸入輸出實例筹裕，可知遍歷路徑醋闭，該遍歷路徑也是最好的路徑，因此只要依次遍歷每個輸出字符串即可
以23為例朝卒，遍歷路徑即為："ad","ae","af","bd","be","bf","cd","ce","cf"证逻，兩外無順序要求
要尋找該路徑的遍歷模型
冒泡式遍歷無法實現(xiàn)，因為無法確定輸入字母集合個數(shù)抗斤。但是可以發(fā)現(xiàn)如”ad“囚企，實際上是位置{0,1}，”ae“也可以是位置{0,2}瑞眼，由此可得龙宏，遍歷路徑可以轉(zhuǎn)換為：
{0,1},{0,2},{0,3},{0,4},{1,0}...，至此可以為該路徑設(shè)計遍歷模型伤疙，可以使用一個可以獲取下一遍歷節(jié)點的迭代器银酗，該迭代器的next操作類似由{m,n}獲取{m,n+1}，當(dāng)位置超出子母個數(shù)時徒像，可以修正該位置
偽代碼實現(xiàn)
- 設(shè)計位置pos結(jié)構(gòu)體黍特，用于表示{m,n}位置
- 寫遍歷框架，基本是調(diào)用迭代器遍歷
- 編寫迭代器next函數(shù)厨姚，基本邏輯為當(dāng)前位置+1衅澈，當(dāng)位置超出時修正
至此可以寫代碼調(diào)試至作題完畢。
題解暫作記錄
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 {
// 若當(dāng)前位數(shù)超出對應(yīng)子母串位數(shù)谬墙，修正當(dāng)前為0今布，下一位加1
if pos.index > len(pos.phoneLetters)-1 {
// 若修正位數(shù)時為最后一位经备，終止
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
}
// 初始化結(jié)果迭代器
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])]
}
// 遍歷結(jié)果集
for phoneResultIterator != nil {
stringRes = append(stringRes, phoneResultIterator.toString())
phoneResultIterator = phoneResultIterator.next()
}
return stringRes
}
func main() {
res := letterCombinations("274")
fmt.Print(res)
}
看題解發(fā)現(xiàn)對于遍歷所有集合有通用解決模型：回溯
回溯專題
后面會做一個回溯的專題訓(xùn)練
回溯基本模型
查閱資料發(fā)現(xiàn)回溯有通用的樸素模型：
result = []
def backtrack(路徑, 選擇列表):
if 滿足結(jié)束條件:
result.add(路徑)
return
for 選擇 in 選擇列表:
做選擇
backtrack(路徑, 選擇列表)
撤銷選擇
回溯經(jīng)典問題
回溯經(jīng)典問題包括：
- N皇后回溯
- 01背包
- 樹深度優(yōu)先遍歷
- 樹廣度優(yōu)先遍歷
電話號碼子母組合回溯解法
回溯解法
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
// 列表：得到下一級決策組，觸發(fā)bt調(diào)用
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)
}
