7.3电话号码的字母组合（LC17-M）

算法：

数字到字母要映射，可以用map，也可以用二维数组，或者直接用一个字符串

这里用字符串，键入的数字对应字符串的索引

String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

为什么要用回溯？

如果键入n个数字，那难道要用n个for循环吗？

可以用回溯。递归来求取组合。

回溯就要画树：

遍历的深度，就是输入"23"的长度（2），

宽度就是每个数字对应的字母个数（3），

叶子节点就是我们要收集的结果，输出["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。

回溯三部曲：

1.确定返回值和参数：

返回值：void

参数：digits（力扣题目里面给的）、Index（确定当前递归遍历到哪里一个数字了）、numString（用于传入字符串）

前两道题目是在一个集合中求组合，需要告诉我们当前已经收获了哪些组会，避免得到重复的组合，才要startindex。而本题在两个集合中（示例中为 2 3）作组合，所以不用startindex。

2.确定终止条件：

index== digits.size()

同时，收获结果

3.单层递归逻辑：

首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。

然后for循环来处理这个字符集，代码如下：

// 将index指向的数字转为int
//digits[index]：确定取的是电话里的哪个数字
//digits[index] - '0':把字符串转为int

int digit = digits[index] - '0';        
string letters = letterMap[digit];      // 取数字对应的字符集
//for循环：i从0开始取，比如abc，从a开始取，然后b c
for (int i = 0; i < letters.size(); i++) {
// 处理，把a Push进来
    s.push_back(letters[i]);      
// 递归
//注意index+1，下一层要处理下一个数字了
//（比如当前index处理的是2对应的字母abc，下一层就要处理3对应的字母def）      
    backtracking(digits, index + 1);
// 回溯  
//  比如在a下面取了d，得到ad，要把d pop掉，再取e，得到ae
    s.pop_back();                      
}

调试过程：

原因：

?`String`?和?`StringBuilder`?类型中找不到?`size()`?和?`add()`?方法。

对于 Java 字符串，应该使用?`length()`?方法来获取字符串的长度，而不是 `size()。

对于?`StringBuilder`，如果要添加字符串，你应该使用?`append()`?方法，而不是?`add()`。

修改后：

原因：

在?`backtracking`?方法中，尝试将?`numString[i]`?的字符附加到?`path`?中，但是应该附加?`str.charAt(i)`?而不是?`numString[i]`。

因为?`str`?包含了当前数字对应的字符串，而不是?`numString`?数组。

这意味着需要将?`path.append(numString[i])`?更改为?`path.append(str.charAt(i))`。这样才能将当前数字对应的字符逐个附加到?`path`?中。

修改后：

原因：问题出在if (digits == "" || digits == null ) return result;

应该改为

 if (digits == null || digits.length() == 0) return result;

或者

if (digits.equals("") || digits == null ) return result;

在 Java 中，使用?`==`?来比较两个字符串是否相等会检查它们是否是同一个对象，而不是检查它们的内容是否相等。因此，当使用?`==`?来比较?`digits`?是否为空字符串时，它实际上检查的是对象的引用是否为相同的对象。

对于字符串内容的比较，应该使用?`equals()`?方法。所以在你代码中，应该使用?`if (digits.equals("") || digits == null)`?来检查字符串是否为空或为 null。

因此，当你使用?`if (digits == "" || digits == null ) return result;`?时，如果?`digits`?是空字符串，条件?`digits == ""`?不会成立，因为它们不是同一个对象。这就是为什么?`result`?不会是空的原因。

正确代码：

class Solution {
    //全局变量List存储结果,path存储当前字符串组合
    List<String> result = new LinkedList<>();
    StringBuilder path = new StringBuilder();
    public List<String> letterCombinations(String digits) {
//处理示例2
    if (digits.equals("") || digits == null ) return result;
    String[] telephone = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"};
    backtracking (digits, 0, telephone);
    return result;

    }
    //回溯函数（递归函数）
    //1.确定返回值和参数
    void backtracking (String digits, int index, String[] numString){
    //2.确定终止条件
    if (index == digits.length()){
        //result是list，path是string,不能直接add
        result.add(path.toString());
        return;
    }
    //3.单层递归逻辑
    //str 表示当前index对应的字符串
    //比如index=2
    String str = numString[digits.charAt(index) - '0'];//str='abc'
    for (int i=0; i<str.length(); i++){

        path.append(str.charAt(i));//i=0,path='a'

        backtracking(digits, index+1, numString);

        path.deleteCharAt(path.length()-1);
    }
    }
}

?Java代码中用到的语法知识：

//每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuildr
    StringBuilder temp = new StringBuilder();

使用了?`StringBuilder`?类来构建字符串。相比于直接对字符串进行拼接操作，使用?`StringBuilder`?可以更高效地进行大量字符串操作，因为字符串是不可变的，每次对字符串进行拼接实际上是创建了新的字符串对象。而?`StringBuilder`?可以就地修改字符串而不创建新的对象，因此在大量字符串操作时，使用?`StringBuilder`?会更加高效。

 //遍历全部一次记录一次得到的字符串
        if (num == digits.length()) {
            list.add(temp.toString());
            return;
        }

`toString`?是 Java 中用于将对象转换为字符串的方法。在这个上下文中，`temp.toString()`?将?`temp`?对象转换为字符串形式，以便将其添加到?`list`?中。

String str = numString[digits.charAt(num) - '0'];

`charAt`?方法是 Java 中用于获取字符串中指定索引处的字符的方法。在给定的上下文中，`str.charAt(i)`?会从字符串?`str`?中检索索引为?`i`?处的字符。然后将这个字符追加到?`temp`?字符串中。

//剔除末尾的继续尝试
 temp.deleteCharAt(temp.length() - 1);

`deleteCharAt`?是 Java 中用于删除字符串中指定位置字符的方法。在这个上下文中，`temp.deleteCharAt(temp.length() - 1)`?会删除?`temp`?字符串中的最后一个字符。

时间空间复杂度：

•