2016年7月21日星期四

[LeetCode] #17 Letter Combinations of a Phone Number

Time complexity: O(C^n), C = 3 or 4
Because T(n) = CT(n - 1)

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        helper(result, new StringBuilder(), digits.toCharArray(), 0);
        return result;
    }
    
    private void helper(List<String> result, StringBuilder sb, char[] chars, int start) {
        if (start == chars.length) {
            result.add(new String(sb));
            return;
        }
        
        for (char c : getLetters(chars[start])) {
            sb.append(c);
            helper(result, sb, chars, start + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    
    private char[] getLetters(char a) {
        switch(a) {
            case '2': return "abc".toCharArray();
            case '3': return "def".toCharArray();
            case '4': return "ghi".toCharArray();
            case '5': return "jkl".toCharArray();
            case '6': return "mno".toCharArray();
            case '7': return "pqrs".toCharArray();
            case '8': return "tuv".toCharArray();
            case '9': return "wxyz".toCharArray();
            default: return "".toCharArray();
        }
    }
}


没有评论:

发表评论