LeetCode #17. Letter Combinations of a Phone Number プログラミング練習

問題：

難易度:　medium
入力:　String
目的: 入力されたケータイのボタンを押した時可能な出力をすべて探せ
出力:　Stringのリスト

ガラケー時代を思い出しましょう。画像にあるように1は何も表しません。2はabc, 3はdef, 4-ghi, 5-jkl, 6-mno, 7-pqrs, 8-tuv, 9-wxyzを表し、0はスペースを表しています。
例の様に、入力が23だった場合、2が表すabcと3が表すdefの組み合わせをすべて出力すればいいのです。

注意すべき事:　

• 0と1は何も表しませんがテストケースにあるので空文字列を用意しましょう。

以下回答です。

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<String>();
        String[] table = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        int num = 0;
        combinations(digits, "", num, table, res);
        return res;
    }
    
    public void combinations(String digits, String curr, int num, String[] table, List res) {
        if (num == digits.length()) {
            if (curr.length() != 0) res.add(curr);
            return;
        }
        String temp = table[digits.charAt(num) - '0'];
        for(int i=0;i<temp.length();i++) {
           String next = curr + temp.charAt(i);
           combinations(digits, next, num+1, table, res);
        }
    }
}

今回はrecursiveで書きました。
典型的なDFS(deep first search)です。
組み合わせ問題はDFSやBFSが得意とする問題なので見たときにまず思い浮ぶ様にしましょう。

今日は以上。
よいプログラミング生活を！