17. Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

200px-telephone-keypad2-svg

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

思路: 收入的数字每一位都对应一组字母, 假设输入”234″, 那得到的组合为:
2 -> “abc”
3 -> “def”
2拿a, 3中依次拿d,e,f => [ad, ae, af]
2拿b, 3中依次拿d,e,f => [bd, be,bf]
2拿c, 3中依次拿d,e,f => [cd, ce,cf]
我们可以用递归的思路来解决, 每次传入一个位置参数pos, 当pos等于digits的长度的时候,把结果加入到list里面。 盛放结果的中间变量,最后不要忘记要去掉最后位置的字母,为了下次递归。

Recursive

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<String>();
        String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        if(digits == null || digits.length() == 0) return res;
        StringBuilder sb = new StringBuilder();
        helper(digits, letters, res, sb, 0);
        return res;
    }

    public void helper(String digits, String[] letters, List<String> res, StringBuilder sb, int pos){
        if (pos == digits.length()) {
            res.add(sb.toString());
            return;
        }    
        String letter = letters[digits.charAt(pos) - '2'];
        for(int i = 0; i < letter.length(); i++) {
            sb.append(letter.charAt(i));
            helper(digits, letters, res, sb, pos + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s