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.

**Understand the problem:**

The problem gives a digit string, return all possible letter combination that the number could represent. Note the the relative order of the number should be reflated in the corresponding strings. For instance, "23", 2 is ahead of 3, so abc should be in front of def as well. For a brute force solution, we can iterate all possible combinations, with the time complexity of O(n^m), where n is the number of characters for each digit, m is the length of the digit string.

**Recursive Solution:**

It is a typical recursive problem, you can mimic the solution of Subset.

**Code (Java):**

public class Solution { public ArrayList<String> letterCombinations(String digits) { ArrayList<String> result = new ArrayList<String>(); if (digits == null) return result; String[] dict = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; StringBuilder sb = new StringBuilder(); letterCombinationsHelper(digits, 0, sb, dict, result); return result; } private void letterCombinationsHelper(String digits, int start, StringBuilder temp, String[] dict, ArrayList<String> result) { if (start >= digits.length()) { result.add(temp.toString()); return; } // char to int int num = digits.charAt(start) - '0'; for (int i = 0; i < dict[num].length(); i++) { temp.append(dict[num].charAt(i)); letterCombinationsHelper(digits, start + 1, temp, dict, result); temp.deleteCharAt(temp.length() - 1); } } }

**Summary:**

This is a very classical permutation and combination problem. All P&C problems share the similar idea of using DFS. Be cautious about that.

## No comments:

## Post a Comment