17. Letter Combinations of a Phone Number

Đề bài

Cho chuỗi digits chỉ gồm các chữ số từ 2 đến 9. Hãy trả về tất cả các tổ hợp chữ cái mà chuỗi số này có thể biểu diễn theo quy ước bàn phím điện thoại.

Bảng ánh xạ số → chữ cái (giống nút bấm điện thoại) như hình bên dưới. Lưu ý: 1 không ánh xạ tới chữ cái nào.

Ví dụ:

Input: "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Lưu ý: Thứ tự các chuỗi trong kết quả có thể là bất kỳ.

Ràng buộc (theo LeetCode):

• 0 <= digits.length <= 4
• digits[i] thuộc ['2'..'9']

Tóm tắt đề

Với mỗi chữ số, ta có một tập chữ cái tương ứng. Hãy sinh ra tất cả chuỗi có độ dài bằng len(digits) bằng cách chọn 1 chữ cái cho từng chữ số theo thứ tự.

Ý tưởng

Trong file này có 3 cách:

• Cách 1 (DFS đệ quy): Backtracking/DFS xây chuỗi từ trái sang phải, mỗi bước thử từng ký tự trong nhóm chữ cái của chữ số hiện tại.
• Cách 2 (không đệ quy): Xây dần danh sách kết quả theo từng chữ số, tương tự “nhân” các tập ký tự (phần code dùng biến toàn cục res/final).
• Cách 3 (Backtracking template): Dùng dict (map) để tra cứu và triển khai đúng mẫu backtracking: chọn → đệ quy → bỏ chọn.

Code

package leetcode

var (
	letterMap = []string{
		" ",    //0
		"",     //1
		"abc",  //2
		"def",  //3
		"ghi",  //4
		"jkl",  //5
		"mno",  //6
		"pqrs", //7
		"tuv",  //8
		"wxyz", //9
	}
	res   = []string{}
	final = 0
)

// Giải pháp 1: DFS
func letterCombinations(digits string) []string {
	if digits == "" {
		return []string{}
	}
	res = []string{}
	findCombination(&digits, 0, "")
	return res
}

func findCombination(digits *string, index int, s string) {
	if index == len(*digits) {
		res = append(res, s)
		return
	}
	num := (*digits)[index]
	letter := letterMap[num-'0']
	for i := 0; i < len(letter); i++ {
		findCombination(digits, index+1, s+string(letter[i]))
	}
	return
}

// Giải pháp 2: Không đệ quy (iterative)
func letterCombinations_(digits string) []string {
	if digits == "" {
		return []string{}
	}
	index := digits[0] - '0'
	letter := letterMap[index]
	tmp := []string{}
	for i := 0; i < len(letter); i++ {
		if len(res) == 0 {
			res = append(res, "")
		}
		for j := 0; j < len(res); j++ {
			tmp = append(tmp, res[j]+string(letter[i]))
		}
	}
	res = tmp
	final++
	letterCombinations(digits[1:])
	final--
	if final == 0 {
		tmp = res
		res = []string{}
	}
	return tmp
}

// Giải pháp 3: Backtracking (tham khảo template backtracking, tương tự DFS)
var result []string
var dict = map[string][]string{
	"2" : []string{"a","b","c"},
	"3" : []string{"d", "e", "f"},
	"4" : []string{"g", "h", "i"},
	"5" : []string{"j", "k", "l"},
	"6" : []string{"m", "n", "o"},
	"7" : []string{"p", "q", "r", "s"},
	"8" : []string{"t", "u", "v"},
	"9" : []string{"w", "x", "y", "z"},
}

func letterCombinationsBT(digits string) []string {
	result = []string{}
	if digits == "" {
		return result
	}
	letterFunc("", digits)
	return result
}

func letterFunc(res string, digits string) {
	if digits == "" {
		result = append(result, res)
		return
	}

	k := digits[0:1]
	digits = digits[1:]
	for i := 0; i < len(dict[k]); i++ {
		res += dict[k][i]
		letterFunc(res, digits)
		res = res[0 : len(res)-1]
	}
}

---