https://leetcode.com/problems/letter-combinations-of-a-phone-number/
Time Complexity: Time complexity of above code is O(4n) where n is number of digits in input number.
X. DFS+Backtracking:
https://github.com/rffffffff007/leetcode/blob/master/Letter%20Combinations%20of%20a%20Phone%20Number.java
Using char array is better than using list<character>
static Map<Character, String> letterMap = new HashMap<Character, String>();
static{
letterMap.put('1', "");
letterMap.put('2', "abc");
letterMap.put('3', "def");
letterMap.put('4', "ghi");
letterMap.put('5', "jkl");
letterMap.put('6', "mno");
letterMap.put('7', "pqrs");
letterMap.put('8', "tuv");
letterMap.put('9', "wxyz");
}
public ArrayList<String> letterCombinations(String digits) {
char[] cs = new char[digits.length()];
ArrayList<String> res = new ArrayList<String>();
appendDigits(digits, 0, cs, res);
return res;
}
private void appendDigits(String digits, int i, char[] cs, ArrayList<String> res){
if(i == digits.length()){
res.add(new String(cs));
return;
}
String letters = letterMap.get(digits.charAt(i));
for(int j = 0; j < letters.length(); j++){
cs[i] = letters.charAt(j);//
appendDigits(digits, i + 1, cs, res);
}
}
https://leetcode.com/articles/letter-combinations-of-a-phone-number/
http://www.lifeincode.net/programming/leetcode-letter-combinations-of-a-phone-number-java/
Use StringBulder
https://discuss.leetcode.com/topic/25657/simple-java-solution-using-recursion
X. Iterative DFS
http://www.cnblogs.com/smileheart/p/4034336.html
X. BFS: Iterative Version
https://zyfu0408.gitbooks.io/interview-preparation/content/bit-manipulation/bitsubsets.html
http://www.jyuan92.com/blog/leetcode-letter-combinations-of-a-phone-number/
当已经获得digits[0:i-1]的所有letter combinations以后，加入digits[i]后新combinations为加入每个可能对应的字母加到之前的解集中。这里需要克隆多份之前的解
http://www.lifeincode.net/programming/leetcode-letter-combinations-of-a-phone-number-java/
Use LinkedList as Queue
HashMapList<String, String> dictionary) {
return dictionary.get(numbers);
}
/* PRECOMPUTATION */
/* Create a hash table that maps from a number to all words that have this
* numerical representation. */
HashMapList<String, String> initializeDictionary(String[] words) {
/* Create a hash table that maps from a letter to the digit */
HashMap<Character, Character> letterToNumberMap = createletterToNumberMap();
/* Create word -> number map. */
HashMaplist<String, String> wordsToNumbers = new HashMaplist<String, String>();
for (String word: words) {
String numbers = convertToT9(word, letterToNumberMap);
wordsToNumbers.put(numbers, word);
}
return wordsToNumbers;
}
/* Convert mapping of number->letters into letter->number. */
HashMap<Character, Character> createletterToNumberMap() {
HashMap<Character, Character> letterToNumberMap
new HashMap<Character, Character>();
for (int i= 0; i < t9Letters.length; i++) {
char[] letters = t9Letters[i];
if (letters != null) {
for (char letter : letters) {
char c = Character.forDigit(i, 10);
letterToNumberMap.put(letter, c);
}
}
}
return letterToNumberMap;
}
/* Convert from a string to its T9 representation. */
String convertToT9(String word, HashMap<Character, Character> letterToNumberMap) {
StringBuilder sb = new StringBuilder();
for (char c : word.toCharArray()) {
if (letterToNumberMap.containsKey(c)) {
char digit = letterToNumberMap.get(c);
sb.append(digit);
}
}
return sb.toString();
}
char[][] t9Letters =/* Same as before */
// HashMaplist<String, Integer> is a HashMap that maps from Strings to Arraylist<Integer>.
Stop recursing down paths which will obviously fail. Specifically, if there are no words in the dictionary that start with prefix, stop recursing
Arraylist<String> getValidT9Words(String number, Trie trie) {
Arraylist<String> results = new Arraylist<String>();
getValidWords(number, 0, "", trie.getRoot(), results);
return results;
}
void getValidWords(String number, int index, String prefix, TrieNode trieNode,
Arraylist<String> results) {
/* If it's a complete word, print it. */
if (index == number.length()) {
if (trieNode.terminates()) {//Is complete word
results.add(prefix);
}
return;
}
/* Get characters that match this digit */
char digit = number.charAt(index);
char[] letters = getT9Chars(digit);
/* Go through all remaining options. */
if (letters != null) {
for (char letter : letters) {
TrieNode child= trieNode.getChild(letter);
/* If there are words that start with prefix + letter,
* then continue recursing. */
if (child != null) {
getValidWords(number, index + 1, prefix + letter, child, results);
}
}
}
ArrayList<String> results = new Arraylist<String>();
getValidWords(number, 0, "", wordList, results);
return results;
}
void getValidWords(String number, int index, String prefix,
HashSet<String> wordSet, Arraylist<String> results) {
/* If it's a complete word, print it. */
if (index == number.length() && wordSet.contains(prefix)) {
results.add(prefix);
return;
}
/* Get characters that match this digit. */
char digit = number.charAt(index);
char[] letters= getT9Chars(digit);
/* Go through all remaining options. */
if (letters != null) {
for (char letter : letters) {
getValidWords(number, index + 1, prefix + letter, wordSet, results);
}
}
}
/* Return array of characters that map to this digit. */
char[] getT9Chars(char digit) {
if (!Character.isDigit(digit)) {
return null;
}
int dig= Character.getNumericValue(digit) - Character.getNumericValue('0');
return t9Letters[dig];
}
/* Mapping of digits to letters. */
char[][] t9Letters = {null, null, {'a', 'b', 'c'}, {'d', 'e', 'f'},
{'g', 'h', 'i'},
{'t', 'u', 'v'},
{'j', 'k', 'l'}, {'m',
{'w', 'x', 'y', 'z'}
'n', 'o'}, {'p', 'q', 'r', 's,},
};
Read full article from 西小瓜: Leetcode: Letter Combinations of a Phone Number
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.
Time Complexity: Time complexity of above code is O(4n) where n is number of digits in input number.
X. DFS+Backtracking:
https://github.com/rffffffff007/leetcode/blob/master/Letter%20Combinations%20of%20a%20Phone%20Number.java
Using char array is better than using list<character>
static Map<Character, String> letterMap = new HashMap<Character, String>();
static{
letterMap.put('1', "");
letterMap.put('2', "abc");
letterMap.put('3', "def");
letterMap.put('4', "ghi");
letterMap.put('5', "jkl");
letterMap.put('6', "mno");
letterMap.put('7', "pqrs");
letterMap.put('8', "tuv");
letterMap.put('9', "wxyz");
}
public ArrayList<String> letterCombinations(String digits) {
char[] cs = new char[digits.length()];
ArrayList<String> res = new ArrayList<String>();
appendDigits(digits, 0, cs, res);
return res;
}
private void appendDigits(String digits, int i, char[] cs, ArrayList<String> res){
if(i == digits.length()){
res.add(new String(cs));
return;
}
String letters = letterMap.get(digits.charAt(i));
for(int j = 0; j < letters.length(); j++){
cs[i] = letters.charAt(j);//
appendDigits(digits, i + 1, cs, res);
}
}
https://leetcode.com/articles/letter-combinations-of-a-phone-number/
- Time complexity : where
Nis the number of digits in the input that maps to 3 letters (e.g.2, 3, 4, 5, 6, 8) andMis the number of digits in the input that maps to 4 letters (e.g.7, 9), andN+Mis the total number digits in the input. - Space complexity : since one has to keep solutions.
Map<String, String> phone = new HashMap<String, String>() {
{
put("2", "abc");
put("3", "def");
put("4", "ghi");
put("5", "jkl");
put("6", "mno");
put("7", "pqrs");
put("8", "tuv");
put("9", "wxyz");
}
};
List<String> output = new ArrayList<String>();
public void backtrack(String combination, String next_digits) {
// if there is no more digits to check
if (next_digits.length() == 0) {
// the combination is done
output.add(combination);
}
// if there are still digits to check
else {
// iterate over all letters which map
// the next available digit
String digit = next_digits.substring(0, 1);
String letters = phone.get(digit);
for (int i = 0; i < letters.length(); i++) {
String letter = phone.get(digit).substring(i, i + 1);
// append the current letter to the combination
// and proceed to the next digits
backtrack(combination + letter, next_digits.substring(1));
}
}
}
public List<String> letterCombinations(String digits) {
if (digits.length() != 0)
backtrack("", digits);
return output;
}
http://www.programcreek.com/2014/04/leetcode-letter-combinations-of-a-phone-number-java/public List<String> letterCombinations(String digits) { HashMap<Integer, String> map = new HashMap<Integer, String>(); 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"); map.put(0, ""); ArrayList<String> result = new ArrayList<String>(); if(digits == null || digits.length() == 0) return result; ArrayList<Character> temp = new ArrayList<Character>(); getString(digits, temp, result, map); return result; } public void getString(String digits, ArrayList<Character> temp, ArrayList<String> result, HashMap<Integer, String> map){ if(digits.length() == 0){ char[] arr = new char[temp.size()]; for(int i=0; i<temp.size(); i++){ arr[i] = temp.get(i); } result.add(String.valueOf(arr)); return; } Integer curr = Integer.valueOf(digits.substring(0,1)); String letters = map.get(curr); for(int i=0; i<letters.length(); i++){ temp.add(letters.charAt(i));// getString(digits.substring(1), temp, result, map); temp.remove(temp.size()-1);//\\backtrack } } |
Use StringBulder
public List<String> letterCombinations(String digits) {
String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> rec = new LinkedList<>();
StringBuilder string = new StringBuilder();//set initial size to digits.size
letterCombinations(digits, 0, letters, string, rec);
return rec;
}
private void letterCombinations(String digits, int number, String[] letters, StringBuilder sb, List<String> rec) {
if (digits.length() == number) {
rec.add(sb.toString());
return;
}
String letter = letters[digits.charAt(number) - '2'];//\\
for (int i = 0; i < letter.length(); i++) {
sb.append(letter.charAt(i));//
letterCombinations(digits, number + 1, letters, string, rec);
sb.deleteCharAt(string.length() - 1); // it's better to call sb.setLength(length-1);
}
}
https://discuss.leetcode.com/topic/25657/simple-java-solution-using-recursion
Map<Integer, List<String>> digitMap = new HashMap<Integer, List<String>>();
Solution() {
digitMap.put(2, Arrays.asList(new String[] {"a", "b", "c"}));
digitMap.put(3, Arrays.asList(new String[] {"d", "e", "f"}));
digitMap.put(4, Arrays.asList(new String[] {"g", "h", "i"}));
digitMap.put(5, Arrays.asList(new String[] {"j", "k", "l"}));
digitMap.put(6, Arrays.asList(new String[] {"m", "n", "o"}));
digitMap.put(7, Arrays.asList(new String[] {"p", "q", "r", "s"}));
digitMap.put(8, Arrays.asList(new String[] {"t", "u", "v"}));
digitMap.put(9, Arrays.asList(new String[] {"w", "x", "y", "z"}));
}
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<String>();
if(digits.length() == 0)
return result;
if(digits.length() == 1)
return digitMap.get(digits.charAt(0) - '0');
List<String> intermediate = letterCombinations(digits.substring(1, digits.length()));
for(String first : digitMap.get(digits.charAt(0) - '0'))
for(String rest : intermediate)
result.add(first + rest);
return result;
}X. Iterative DFS
http://www.cnblogs.com/smileheart/p/4034336.html
X. BFS: Iterative Version
https://zyfu0408.gitbooks.io/interview-preparation/content/bit-manipulation/bitsubsets.html
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<String>();
if (digits == null || digits.length() == 0) {
return result;
}
String[] strs = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
result.add("");
for (int i = 0; i < digits.length(); i++) {
int num = digits.charAt(i) - '0';
String str = strs[num];
List<String> nextLvl = new ArrayList<String>();
for (String s: result) {
for (int j = 0; j < str.length(); j++) {
nextLvl.add(s + str.charAt(j));
}
}
result = nextLvl;
}
return result;
}
This is a iterative solution. For each digit added, remove and copy every element in the queue and add the possible letter to each element, then add the updated elements back into queue again. Repeat this procedure until all the digits are iterated.
public List<String> letterCombinations(String digits) {
LinkedList<String> ans = new LinkedList<String>();
if(digits.isEmpty()) return ans;
String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
ans.add("");
for(int i =0; i<digits.length();i++){
int x = Character.getNumericValue(digits.charAt(i));
while(ans.peek().length()==i){
String t = ans.remove();
for(char s : mapping[x].toCharArray())
ans.add(t+s);
}
}
return ans;
}
A version without first loop, but same time complexity. Both are single queue BFS solutions.:
public List<String> letterCombinations(String digits) {
LinkedList<String> ans = new LinkedList<String>();
if(digits.isEmpty()) return ans;
String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
ans.add("");
while(ans.peek().length()!=digits.length()){
String remove = ans.remove();
String map = mapping[digits.charAt(remove.length())-'0'];
for(char c: map.toCharArray()){
ans.addLast(remove+c);
}
}
return ans;
}http://www.jyuan92.com/blog/leetcode-letter-combinations-of-a-phone-number/
public static List<String> letterCombinations(String digits) {
String digitletter[] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
List<String> result = new ArrayList<String>();
if (digits.length()==0) return result;
result.add("");
for (int i=0; i<digits.length(); i++)
result = combine(digitletter[digits.charAt(i)-'0'],result);
return result;
}
public static List<String> combine(String digit, List<String> l) {
List<String> result = new ArrayList<String>();
for (int i=0; i<digit.length(); i++)
for (String x : l)
result.add(x+digit.charAt(i));
return result;
}
public List<String> letterCombinationsBFS(String digits) {
List<String> res = new LinkedList<String>();
if (null == digits || digits.length() == 0) {
return res;
}
res.add("");
String[] keyboards = new String[]{" ", "", "abc", "def",
"ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
for (int i = 0; i < digits.length(); i++) {
String keyboard = keyboards[digits.charAt(i) - '0'];
List<String> list = new LinkedList<String>();
for (String cur : res) {
for (int k = 0; k < keyboard.length(); k++) {
list.add(cur + keyboard.charAt(k));
}
}
res = list;
}
return res;
}
http://www.lifeincode.net/programming/leetcode-letter-combinations-of-a-phone-number-java/
public List<String> letterCombinations(String digits) {
String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
LinkedList<String> list = new LinkedList<>();
list.add("");
for (int i = 0; i < digits.length(); i++) {
int num = digits.charAt(i) - '2';//???
int size = list.size();
for (int k = 0; k < size; k++) {
String tmp = list.pop(); // change to removeFirst
for (int j = 0; j < letters[num].length(); j++)
list.add(tmp + letters[num].charAt(j));
}
}
List<String> rec = new LinkedList<>();
rec.addAll(list);//??? why not directly return list
return rec;
}
https://leetcode.com/discuss/29404/easy-understand-java-solution
method combine is to add new letters to old list, using 2 for-loop.
for example:
gave digits = "23"
i=0 -> result=combine("abc", [""]) ---> [a,b,c];
i=1 -> result=combine("def", [a,b,c]) ---> [ad,bd,cd, ae,be,ce, af,bf,cf];
public class Solution {
public static List<String> letterCombinations(String digits) {
String digitletter[] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
List<String> result = new ArrayList<String>();
if (digits.length()==0) return result;
result.add("");
for (int i=0; i<digits.length(); i++)
result = combine(digitletter[digits.charAt(i)-'0'],result);
return result;
}
public static List<String> combine(String digit, List<String> l) {
List<String> result = new ArrayList<String>();
for (int i=0; i<digit.length(); i++)
for (String x : l)
result.add(x+digit.charAt(i));
return result;
}
}
层次遍历，从左往右依次读取数字，将解析的字母加入到之前解析的结果中。由于题目要求输出所有的结果，所以时间复杂度和空间复杂度都和输出成正比，为O(3^N)~O(4^N)之间。由于解析新的数字是加在前一个数字的解析结果之上，所有也可以理解为动态规划。
https://chazyhabit.wordpress.com/2014/08/12/letter-combinations-of-a-phone-number-leetcode-48/ public List<String> letterCombinations(String digits) { List<String> result = new ArrayList<String>(); if(digits==null) return result; char[] digitsAry = digits.toCharArray(); ArrayList<StringBuilder> parent = new ArrayList<StringBuilder>(); parent.add(new StringBuilder()); HashMap<Character, char[]> dict = new Dictionary().dict; for(char digit : digitsAry) { if(digit=='0'||digit=='1') continue; // just check list!=null ArrayList<StringBuilder> current = parent; parent = new ArrayList<StringBuilder>(); char[] list = dict.get(digit); for(StringBuilder sb : current) { for(char c : list) { StringBuilder newSb = new StringBuilder(sb); newSb.append(c); parent.add(newSb); } } } for(StringBuilder sb : parent) result.add(sb.toString()); return result; } class Dictionary { HashMap<Character, char[]> dict; Dictionary() { dict = new HashMap<Character, char[]>(); char[] char2 = {'a', 'b', 'c'}; char[] char3 = {'d', 'e', 'f'}; char[] char4 = {'g', 'h', 'i'}; char[] char5 = {'j', 'k', 'l'}; char[] char6 = {'m', 'n', 'o'}; char[] char7 = {'p', 'q', 'r', 's'}; char[] char8 = {'t', 'u', 'v'}; char[] char9 = {'w', 'x', 'y', 'z'}; dict.put('2', char2 ); dict.put('3', char3 ); dict.put('4', char4 ); dict.put('5', char5 ); dict.put('6', char6 ); dict.put('7', char7 ); dict.put('8', char8 ); dict.put('9', char9 ); } } Use LinkedList as Queue
public List<String> letterCombinations(String digits) {
String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
LinkedList<String> list = new LinkedList<>();
list.add("");
for (int i = 0; i < digits.length(); i++) {
int num = digits.charAt(i) - '2';
int size = list.size();
for (int k = 0; k < size; k++) {
String tmp = list.pop();
for (int j = 0; j < letters[num].length(); j++)
list.add(tmp + letters[num].charAt(j));
}
}
List<String> rec = new LinkedList<>();
rec.addAll(list);
return rec;
}
X. Getting the words that map to this number will run inO(N) time, where N is the number of digits.
1. Create a hash table that maps from a sequence of digits to a list of strings.
1. Create a hash table that maps from a sequence of digits to a list of strings.
2. Go through each word in the dictionary and convert it to its T9 representation (e.g., APPLE - > 27753).
Store each of these in the above hash table. For example, 8733 would map to {used, tree}.
ArrayList<String> getValidT9Words(String numbers,HashMapList<String, String> dictionary) {
return dictionary.get(numbers);
}
/* PRECOMPUTATION */
/* Create a hash table that maps from a number to all words that have this
* numerical representation. */
HashMapList<String, String> initializeDictionary(String[] words) {
/* Create a hash table that maps from a letter to the digit */
HashMap<Character, Character> letterToNumberMap = createletterToNumberMap();
/* Create word -> number map. */
HashMaplist<String, String> wordsToNumbers = new HashMaplist<String, String>();
for (String word: words) {
String numbers = convertToT9(word, letterToNumberMap);
wordsToNumbers.put(numbers, word);
}
return wordsToNumbers;
}
/* Convert mapping of number->letters into letter->number. */
HashMap<Character, Character> createletterToNumberMap() {
HashMap<Character, Character> letterToNumberMap
new HashMap<Character, Character>();
for (int i= 0; i < t9Letters.length; i++) {
char[] letters = t9Letters[i];
if (letters != null) {
for (char letter : letters) {
char c = Character.forDigit(i, 10);
letterToNumberMap.put(letter, c);
}
}
}
return letterToNumberMap;
}
/* Convert from a string to its T9 representation. */
String convertToT9(String word, HashMap<Character, Character> letterToNumberMap) {
StringBuilder sb = new StringBuilder();
for (char c : word.toCharArray()) {
if (letterToNumberMap.containsKey(c)) {
char digit = letterToNumberMap.get(c);
sb.append(digit);
}
}
return sb.toString();
}
char[][] t9Letters =/* Same as before */
// HashMaplist<String, Integer> is a HashMap that maps from Strings to Arraylist<Integer>.
Stop recursing down paths which will obviously fail. Specifically, if there are no words in the dictionary that start with prefix, stop recursing
Arraylist<String> getValidT9Words(String number, Trie trie) {
Arraylist<String> results = new Arraylist<String>();
getValidWords(number, 0, "", trie.getRoot(), results);
return results;
}
void getValidWords(String number, int index, String prefix, TrieNode trieNode,
Arraylist<String> results) {
/* If it's a complete word, print it. */
if (index == number.length()) {
if (trieNode.terminates()) {//Is complete word
results.add(prefix);
}
return;
}
/* Get characters that match this digit */
char digit = number.charAt(index);
char[] letters = getT9Chars(digit);
/* Go through all remaining options. */
if (letters != null) {
for (char letter : letters) {
TrieNode child= trieNode.getChild(letter);
/* If there are words that start with prefix + letter,
* then continue recursing. */
if (child != null) {
getValidWords(number, index + 1, prefix + letter, child, results);
}
}
}
This algorithm runs in O( 4N ) time, where N is the length of the string. This is because we recursively branch four times for each call to getValidWords, and we recurse until a call stack depth of N.
ArrayList<String> getValidT9Words(String number, HashSet<String> wordList) {ArrayList<String> results = new Arraylist<String>();
getValidWords(number, 0, "", wordList, results);
return results;
}
void getValidWords(String number, int index, String prefix,
HashSet<String> wordSet, Arraylist<String> results) {
/* If it's a complete word, print it. */
if (index == number.length() && wordSet.contains(prefix)) {
results.add(prefix);
return;
}
/* Get characters that match this digit. */
char digit = number.charAt(index);
char[] letters= getT9Chars(digit);
/* Go through all remaining options. */
if (letters != null) {
for (char letter : letters) {
getValidWords(number, index + 1, prefix + letter, wordSet, results);
}
}
}
/* Return array of characters that map to this digit. */
char[] getT9Chars(char digit) {
if (!Character.isDigit(digit)) {
return null;
}
int dig= Character.getNumericValue(digit) - Character.getNumericValue('0');
return t9Letters[dig];
}
/* Mapping of digits to letters. */
char[][] t9Letters = {null, null, {'a', 'b', 'c'}, {'d', 'e', 'f'},
{'g', 'h', 'i'},
{'t', 'u', 'v'},
{'j', 'k', 'l'}, {'m',
{'w', 'x', 'y', 'z'}
'n', 'o'}, {'p', 'q', 'r', 's,},
};
Read full article from 西小瓜: Leetcode: Letter Combinations of a Phone Number
