题目

17、电话号码的字母组合

思路

1. 输入处理：

   • 接收一个字符串 digits，表示手机键盘上的数字，数字可以对应不同的字母组合。

2. 边界检查：

   • 如果输入字符串 digits 为空，返回一个空的结果列表。

3. 按钮映射：

   • 初始化一个二维数组 buttons，它将每个数字映射到相应的字母（如 2 对应 “abc”，3 对应 “def”，等）。
   • 使用一个计数器，将字母依次填充到对应数字的按钮数组中。

4. 转换输入为字符数组：

   • 将输入字符串 digits 转换为字符数组 digitsArr，便于后续处理。

5. 递归深度优先搜索 (DFS)：

   • 定义一个递归函数 dfs，用于生成字母组合。
   • 函数参数包含当前的数字数组、按钮映射、结果列表、当前字母组合以及当前数字索引。

6. 生成组合：

   • 检查当前的数字索引 digitIndex 是否已达到输入数字数组的大小。
   • 如果达到，表示已生成一个有效的字母组合，添加到结果列表中。
   • 如果未达到，则根据当前数字对应的按钮，循环每个字母，递归调用 DFS 函数，构建下一个字母组合。

7. 返回结果：

   • 一旦 DFS 完成所有递归调用，返回最终的字母组合列表 ans。

这个程序的核心思路是利用递归逐层构建字母组合，直到遍历完所有数字的可能字母。通过使用回溯方法（DFS），实现了对于所有可行组合的探索和累积。

代码

class Solution {func dfs(digitsArr: Array<Rune>, buttons: ArrayList<ArrayList<Rune>>, ans: ArrayList<String>, str: ArrayList<Rune>, digitIndex: Int64):Unit{if(digitIndex == digitsArr.size){ans.append(String(str))return}// println(digitsArr[digitIndex])// println(UInt32(digitsArr[digitIndex]))// println("check buttons ${Int64(UInt32(digitsArr[digitIndex]) - UInt32(r'0') - 1)}")for(c in buttons[Int64(UInt32(digitsArr[digitIndex]) - UInt32(r'0') - 1)]){var newStr = ArrayList<Rune>(str)newStr.append(c)dfs(digitsArr, buttons,ans, newStr, digitIndex+1)}}func letterCombinations(digits: String): ArrayList<String> {if(digits.size == 0){return ArrayList<String>()}var buttons = ArrayList<ArrayList<Rune>>()let cInButton = [0,3,3,3,3,3,4,3,4]var cnt:UInt32 = 0for(i in 0..9){var button = ArrayList<Rune>()for(j in 0..cInButton[i]){button.append(Rune(UInt32(r'a')+cnt))// println("char ${Rune(UInt32(r'a')+cnt)} is append to button ${i+1}")cnt++}buttons.append(button)// println()}// for(button in buttons){//     println("1")//     println(String(button))// }let digitsArr = digits.toRuneArray()var ans = ArrayList<String>()// println("start dfs")dfs(digitsArr, buttons, ans, ArrayList<Rune>(), 0)// println()return ans}
}

复杂度

时间复杂度：O(4^n) （其中 n 是输入字符串的长度）

空间复杂度：O(n) （用于递归栈和存储结果）

遇到的坑

1、array初始化问题
一开始想着直接写死

class Solution {func letterCombinations(digits: String): ArrayList<String> {let teles = [[],[r'a', r'b', r'c'],[r'd', r'e', r'f'],[r'g', r'h', r'i'],[r'i', r'k', r'l'],[r'm', r'n', r'o'],[r'p', r'q', r'r', r's'],[r't', r'u', r'v'],[r'w', r'x', r'y', r'z']]for(tele in teles){println(String(tele))}return ArrayList<String>()}
}

报错

error: array literal type cannot be inferred==> solution.cj:3:22:|3 |         let teles = [[],[r'a', r'b', r'c'],[r'd', r'e', r'f'],[r'g', r'h', r'i'],[r'i', r'k', r'l'],[r'm', r'n', r'o'],[r'p', r'q', r'r', r's'],[r't', r'u', r'v'],[r'w', r'x', r'y', r'z']]|                      ^|

想着把类型写上去

class Solution {func letterCombinations(digits: String): ArrayList<String> {let teles = Array<Array<Rune>>[[],[r'a', r'b', r'c'],[r'd', r'e', r'f'],[r'g', r'h', r'i'],[r'i', r'k', r'l'],[r'm', r'n', r'o'],[r'p', r'q', r'r', r's'],[r't', r'u', r'v'],[r'w', r'x', r'y', r'z']]for(tele in teles){println(String(tele))}return ArrayList<String>()}
}

报错

error: extra arguments given for parameter list '(Int64, (Int64) -> Generics-T)' in call==> solution.cj:3:39:|3 |         let teles = Array<Array<Rune>>((),(r'a', r'b', r'c'),(r'd', r'e', r'f'),(r'g', r'h', r'i'),(r'i', r'k', r'l'),(r'm', r'n', r'o'),(r'p', r'q', r'r', r's'),(r't', r'u', r'v'),(r'w', r'x', r'y', r'z'))|                                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected 2 arguments, found 9|
note: found candidate==> (package std.core)array.cj:40:12:

按个赋值

class Solution {func letterCombinations(digits: String): ArrayList<String> {var teles = Array<Array<Rune>>(10, item: Array<Rune>(4, item: r'0'))for(i in 0..10){for(j in 0..4){print(teles[i][j])}println()}teles[2][0] = r'a'teles[2][1] = r'b'teles[2][2] = r'c'teles[3][0] = r'd'teles[3][1] = r'e'teles[3][2] = r'f'teles[4][0] = r'g'teles[4][1] = r'h'teles[4][2] = r'i'teles[5][0] = r'j'teles[5][1] = r'k'teles[5][2] = r'l'teles[6][0] = r'm'teles[6][1] = r'n'teles[6][2] = r'o'teles[7][0] = r'p'teles[7][1] = r'q'teles[7][2] = r'r'teles[7][3] = r's'teles[8][0] = r't'teles[8][1] = r'u'teles[8][2] = r'v'teles[9][0] = r'w'teles[9][1] = r'x'teles[9][2] = r'y'teles[9][3] = r'z'// for(tele in teles){//     println(String(tele))// }for(i in 0..10){for(j in 0..4){print(teles[i][j])}println()}return ArrayList<String>()}
}

倒是没报错，但是跑出来不对

目测是var teles = Array<Array<Rune>>(10, item: Array<Rune>(4, item: r'0'))的Array<Rune>(4, item: r'0')指向的是同一个引用，导致所有的array都变成了最后一次修改的结果
目前是放弃了array，已老实用ArrayList
2、试了下append©，比insert(size, c)好用多了

结果

cangjie