Letter Combinations of a Phone Number


#1

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.

Example:

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

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.


#2

Solution for letter combinations of a phone number leetcode in Golang.

func letterCombinations(digits string) []string {
    dmap := map[string]string{
        "2" : "abc",
        "3" : "def",
        "4" : "ghi",
        "5" : "jkl",
        "6" : "mno",
        "7" : "pqrs",
        "8" : "tuv",
        "9" : "wxyz",
    }
    result := make([]string, 0)
    for _, digit := range digits {
        newResult := make([]string, 0)
        for _, ch := range dmap[string(digit)]{
            if len(result)==0{
                 newResult = append(newResult,string(ch))
            }else {
                for _, val := range result{
                    newResult = append(newResult,val+string(ch))
                 }
             }   
        }
      fmt.Println(newResult)
      result = newResult
    }
    return result
}

#3

Similar implementation but without the extra temp newResult array.

func letterCombinations(digits string) []string {
    result := make([]string, 0)
    if len(digits) == 0{
        return result
    }
    dmap := map[string]string{
        "2" : "abc",
        "3" : "def",
        "4" : "ghi",
        "5" : "jkl",
        "6" : "mno",
        "7" : "pqrs",
        "8" : "tuv",
        "9" : "wxyz",
    }
   
    result = append(result, "")
    for i:=0; i<len(digits);i++ {
        for i == len(result[0]){
            f := result[0]
            result = result[1:]
            for _, ch := range dmap[string(digits[i])] {
                result = append(result, f+string(ch))
            }
        }
    }
    
    return result
}

#4

Same approach in Java.

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if(digits==null || digits.length()==0) return result;
        HashMap<Character, String> map = new HashMap<>();
        map.put('2', "abc");  map.put('3', "def");  map.put('4', "ghi");
        map.put('5', "jkl");  map.put('6', "mno");  map.put('7', "pqrs");
        map.put('8', "tuv");  map.put('9', "wxyz");
        Queue<String> queue = new LinkedList<>();
        queue.offer("");
        for(char digit : digits.toCharArray()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                String s = queue.poll();
                for(char ch : map.get(digit).toCharArray()){
                    queue.offer(s+ch);
                }
            }
        }
        
        while(!queue.isEmpty()){
            result.add(queue.poll());
        }
        
        return result;
    }
}