Question

Formatted question description: https://leetcode.ca/all/17.html

17	Letter Combinations of a Phone Number

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"].

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

@June.18,2017:
	variation-1: input with duplicate digits "222222", then it's a duplicate reduction process
					maybe need to pre-sort the charArray of string
	variation-2: now the result combination string length is the same as in put string
					but result string length could from 1 to input string length
					also duplicate issue. "222" -> a,b,c,aa,ab,ac,bb,bc,cc,aaa,aab,aac,....ccc
					I'll use set of string to avoid duplicated string...
@tag-string

Algorithm

Similar topics include Path Sum II, Subsets II, Permutations, Permutations II, Combinations, Combination Sum and Combination Sum II and so on.

Here you can use recursive Recursion to solve, you need to build a dictionary to store the string represented by each number, and then you need a variable level, which records the number of characters in the currently generated string, and realizes the routine and the above questions. similar. In the recursive function, the level is first judged. If the number of digits in digits is equal, the current combination is added to the result res, and then returned. We pass the number in digits to the dict to extract the string, then traverse the extracted string, add each character to the current combination, and call the recursive function.

Code

Java

  • import java.util.ArrayList;
    import java.util.List;
    
    public class Letter_Combinations_of_a_Phone_Number {
    
    	public class Solution {
    
    	    List<String> list = new ArrayList<String>();
    	    ArrayList<String> eachDigit = new ArrayList<String>();
    	    StringBuilder one = new StringBuilder();
    
    	    public List<String> letterCombinations(String s) {
    
    	        if (s == null)   return list;
    	        if (s.length() == 0)    {   list.add("");  return list; }
    
    	        String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // number 0, 1 is empty string
    
    	        for (int i = 0; i < s.length(); i++) {
    	            int num = s.charAt(i) - '0';
    	            eachDigit.add(map[num]); // possible out of boundary, assumption is valid input
    	        }
    
    	        dfs(eachDigit, 0, s.length());
    
    	        return list;
    	    }
    
    	    public void dfs(ArrayList<String> eachDigit, int index, int totalSize) {
    
    	        if (index == totalSize) {
    	            list.add(new String(one)); // or, just pass in a result string, and avoid append() then deleteLast()
    	            return;
    	        }
    
    	        String current = eachDigit.get(index);
    	        for (int i = 0; i < current.length(); i++) {
    	            one.append(current.charAt(i));
    	            dfs(eachDigit, index + 1, totalSize);
    	            one.deleteCharAt(one.length() - 1); // if string, then it's s.substring(0, s.length() - 1)
    	        }
    	    }
    	}
    }
    
    
  • // OJ: https://leetcode.com/problems/letter-combinations-of-a-phone-number/
    // Time: O(4^N)
    // Space: O(N)
    class Solution {
        vector<string> m{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> ans;
        void dfs(string &digits, int start, string &str) {
            if (start == digits.size()) {
                ans.push_back(str);
                return;
            }
            for (char c : m[digits[start] - '2']) {
                str.push_back(c);
                dfs(digits, start + 1, str);
                str.pop_back();
            }
        }
    public:
        vector<string> letterCombinations(string digits) {
            if (digits.empty()) return {};
            string str;
            dfs(digits, 0, str);
            return ans;
        }
    };
    
  • class Solution(object):
      def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if len(digits) == 0:
          return []
    
        d = {1: "", 2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}
    
        def dfs(digits, index, path, res, d):
          if index == len(digits):
            res.append("".join(path))
            return
    
          digit = int(digits[index])
          for c in d.get(digit, []):
            path.append(c)
            dfs(digits, index + 1, path, res, d)
            path.pop()
    
        res = []
        dfs(digits, 0, [], res, d)
        return res
    
    

All Problems

All Solutions