【算法刷题 | 回溯思想 02】4.12（电话号码的字母组合）

4.电话号码的字母组合

4.1问题

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

• 示例一：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

4.2解法：回溯

4.2.1回溯思路

• 注意：
  • 前面两个题目（组合、组合总和||）是在同一个集合中求组合
  • 该题是在不同集合中求组合

List<String> res：最终返回结果
StringBuffer paths：当前路径
String[] numsString={
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
}

（1）函数返回值以及参数

• digits：题目给的数字字符串
• cur：当前遍历的第几个数字

private void backtracking(String digits,int cur)

（2）终止条件

if( cur == digits.length() ){
    res.add( paths.toString() );
    return;
}

（3）遍历过程

String arr=numsString[ digits.charAt(cur)-'0' ];//取出对应数字的字符串

for(int i=0;i<arr.length();i++){//遍历字符串
    paths.append(arr[i]);
    backtracking(digits,cur+1);
    //回溯
    paths.deleteCharAt(paths.size()-1);
}

4.2.2代码实现

class Solution {

    List<String> res=new ArrayList<>();
    StringBuffer paths=new StringBuffer();
    String[] numsString={
    "",
    "",
    "abc",
    "def",
    "ghi",
    "jkl",
    "mno",
    "pqrs",
    "tuv",
    "wxyz"
    };
    
    public List<String> letterCombinations(String digits) {
        if(digits.length()==0){
            return res;
        }
        backtracking(digits,0);
        return res;
    }

    private void backtracking(String digits,int cur){
        if( cur == digits.length() ){
            res.add( paths.toString() );
            return;
        }
        String arr=numsString[ digits.charAt(cur)-'0' ];//取出对应数字的字符串

        for(int i=0;i<arr.length();i++){//遍历字符串
            paths.append(arr.charAt(i));
            backtracking(digits,cur+1);
            //回溯
            paths.deleteCharAt(paths.length()-1);
        }
    }
}

原文地址：https://blog.csdn.net/weixin_61440595/article/details/137669140

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！