友链
姚屹晨

leetcode - [17] Letter Combinations of a Phone Number

2020/06/19

问题描述

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

给你一个字符串，其中都是2-9的正整数，分别对应电话上按钮的数字和字母组合，求固定长度、不同字母排列组合。

举个例子：

Update at 2020_0908

此题需要注意，每个数字都对应属于自己的字符，所以每次递归遍历对于u只需要+1即可。

来看下示意图：

再来看下实现：

class Solution {

    String[] alphas = {
        "", "", "abc", "def", 
        "ghi", "jkl", "mno", 
        "pqrs", "tuv", "wxyz"
    };
    List<String> ans = new LinkedList<>();

    private void dfs(String s, int u, StringBuilder sb){
        if (u == s.length()){
            ans.add(new String(sb));
            return;
        }

        int n = s.charAt(u) - '0';
        for (char c: alphas[n].toCharArray()){
            sb.append(c);
            dfs(s, u + 1, sb);
            sb.setLength(sb.length() - 1);
        }
    }

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) return ans;
        dfs(digits, 0, new StringBuilder());
        return ans;
    }
}

解法1

Thanks @davidluoyes

先来看下示意图：

老规矩，递归函数需要哪些参数？

我需要一个存储最终结果的字符串列表ans，一个临时字符串child，

还有一个指向原始字符串digits中数字的索引start。

然后，我们依次遍历原始字符串digits中的数字，

注意，定位到一个数字后，还需要继续遍历其代表的字母。

所以，递归函数中的遍历每次都需要从0开始。

接着，什么时候将临时字符串child存入最终结果列表ans？

当前索引等于原始字符串的长度： start = digits.length()。

来看下实现：

class Solution {
    
    private final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    public List<String> letterCombinations(String digits) {

        List<String> ans = new LinkedList<>();
        if (digits.length() == 0) return ans;
        bt(ans, digits, 0, new StringBuilder());
        return ans;
    }
    
    private void bt(List<String> ans, String digits, int start, StringBuilder sb){

        if (start == digits.length()){
            ans.add(new String(sb));
            return;
        }
        
        int num = digits.charAt(start) - '0';
        // Be careful: i = 0
        for (int i = 0; i < KEYS[num].length(); i++){
            sb.append(KEYS[num].charAt(i));
            bt(ans, digits, start + 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

（转载本站文章请注明作者和出处 姚屹晨-yaoyichen）

Post Directory