Leetcode–Letter Combinations of a Phone Number

The Problem:

Given a digit string, 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.

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

Notes:

  1. Similar to Combinations, just list every combination.
  2. I tried using StringBuffer instead of String, the speed doesn’t show a big difference, but code gets less concise. Anyway, I think StringBuffer is a better choice and will show advantage when test cases gets bigger.

Java Solution

public class Solution {
    public List<String> letterCombinations(String digits) {
        String[] letters= {" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        List<String> res = new ArrayList<String>();
        if(digits==null || digits.length()==0){
            res.add("");
            return res;
        }
        
        for(int i = 0; i < digits.length(); i++){
            if(letters[digits.charAt(i)-'0'].length()!=0){
                List<String> temp = new ArrayList<String>();
                for(int j = 0; j < letters[digits.charAt(i)-'0'].length(); j++){
                    if(res.size()==0){
                        temp.add(""+letters[digits.charAt(i)-'0'].charAt(j));
                    }
                    else{
                        for(String s: res){
                            temp.add(s+letters[digits.charAt(i)-'0'].charAt(j));
                        }
                    }
                }
                res = temp;
            }
        }
       
        return res;
    }
}
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