How can I print all possible letter combinations that a given phone number can represent?

Question

I just tried my first programming interview, and one of the questions was to write a program that gave a 7-digit phone number, could print all possible letter combinations that each number can represent.

The second part of the question was similar to the question of whether it was a 12-digit international number? How it will affect your design.

I do not have the code that I wrote in the interview, but I got the impression that he was not happy with this.
What is the best way to do this?

Answer 1

In Python, iterative:

digit_map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz', } def word_numbers(input): input = str(input) ret = [''] for char in input: letters = digit_map.get(char, '') ret = [prefix+letter for prefix in ret for letter in letters] return ret 

ret - list of results; first it is filled with one element, an empty string. Then, for each character in the input line, he scans a list of letters that match him from the dict defined at the top. He then replaces the ret list with each combination of an existing prefix and a possible letter.

Answer 2

This seems like a question about letter combinations of a phone number , here is my solution.
This works for an arbitrary number of digits until the result exceeds the memory limit.

 import java.util.HashMap; public class Solution { public ArrayList<String> letterCombinations(String digits) { ArrayList<String> res = new ArrayList<String>(); ArrayList<String> preres = new ArrayList<String>(); res.add(""); for(int i = 0; i < digits.length(); i++) { String letters = map.get(digits.charAt(i)); if (letters.length() == 0) continue; for(String str : res) { for(int j = 0; j < letters.length(); j++) preres.add(str + letters.charAt(j)); } res = preres; preres = new ArrayList<String>(); } return res; } static final HashMap<Character,String> map = new HashMap<Character,String>(){{ put('1', ""); put('2',"abc"); put('3',"def"); put('4',"ghi"); put('5',"jkl"); put('6',"mno"); put('7',"pqrs"); put('8',"tuv"); put('9',"wxyz"); put('0', ""); }} ; } 

I'm not sure how 12-digit international numbers affect design.

Change: International numbers will also be processed.

Answer 3

In Java using recursion:

 import java.util.LinkedList; import java.util.List; public class Main { // Number-to-letter mappings in order from zero to nine public static String mappings[][] = { {"0"}, {"1"}, {"A", "B", "C"}, {"D", "E", "F"}, {"G", "H", "I"}, {"J", "K", "L"}, {"M", "N", "O"}, {"P", "Q", "R", "S"}, {"T", "U", "V"}, {"W", "X", "Y", "Z"} }; public static void generateCombosHelper(List<String> combos, String prefix, String remaining) { // The current digit we are working with int digit = Integer.parseInt(remaining.substring(0, 1)); if (remaining.length() == 1) { // We have reached the last digit in the phone number, so add // all possible prefix-digit combinations to the list for (int i = 0; i < mappings[digit].length; i++) { combos.add(prefix + mappings[digit][i]); } } else { // Recursively call this method with each possible new // prefix and the remaining part of the phone number. for (int i = 0; i < mappings[digit].length; i++) { generateCombosHelper(combos, prefix + mappings[digit][i], remaining.substring(1)); } } } public static List<String> generateCombos(String phoneNumber) { // This will hold the final list of combinations List<String> combos = new LinkedList<String>(); // Call the helper method with an empty prefix and the entire // phone number as the remaining part. generateCombosHelper(combos, "", phoneNumber); return combos; } public static void main(String[] args) { String phone = "3456789"; List<String> combos = generateCombos(phone); for (String s : combos) { System.out.println(s); } } } 

Answer 4

The obvious solution is a function that maps a digit to a list of keys, and then a function that generates possible combinations:

The first is obvious, the second is more problematic, because you have about 3 digits of combinations of digits, which can be a very large number.

One way to do this is to look at each possibility of matching the numbers as a number in the number (based on 4) and implement something close to the counter (jumping over some instances, since there are usually less than 4 letters displayed on a number).

More obvious solutions might be nested loops or recursion, which are less elegant but, in my opinion, valid.

Another thing to be careful about is to avoid scalability issues (e.g., store features in memory, etc.), since we are talking about a lot of combinations.

PS Another interesting continuation of the issue will be localization.

Answer 5

In C ++ (recursive):

 string pattern[] = {"0",".,!","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"}; ofstream keyout("keypad.txt"); void print_keypad(char* str, int k, vector<char> patt, int i){ if(str[k] != '\0') { int x = str[k] - '0'; for(int l = 0; l < pattern[x].length(); l++) { patt[i] = pattern[x][l]; print_keypad(str, k+1, patt, i+1); } keyout << endl; } else if(i == k) { string st(patt.data()); keyout << st << endl; return; } } 

This function can be called with 'k' and 'i' equal to zero.

Anyone who needs more illustrations to understand logic can combine the recursion method with the following output:

 ADG ADH ADI AEG AEH AEI AFG AFH AFI BDG BDH BDI BEG BEH BEI BFG BFH ... 

Answer 6

In numeric keypads, texts and numbers are placed on the same key. For example, 2 has "ABC", if we want to write something starting with "A", we must enter key 2 once. If we would like to type “B,” press the key 2 twice and three times to enter “C. This keyboard is shown below.

keyboard http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard.png

Considering the keyboard, as shown in the diagram, and the number of n digits, list all the words that are possible by clicking these numbers.

For example, if the input number is 234, possible words that can be formed (in alphabetical order): adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi

First we do some calculations. How many words are possible with seven digits with each digit representing n letters? For the first digit, we have no more than four options, and for each choice for the first letter, we have no more than four options for the second digit, and so on. Therefore, his simple math will be O (4 ^ n). Since the keys 0 and 1 do not have the corresponding alphabet, and many characters have 3 characters, 4 ^ n will be the upper limit of the number of words, not the minimum words.

Now let's do some examples.

For the number above 234. Do you see any pattern? Yes, we notice that the last character is always either G, H or I, and whenever it resets its value from I to G, the number to the left of it changes. Similarly, when the second last alphabet resets its meaning, the third last alphabet receives changes and so on. The first character is reset only once, when we generated all the words. This can be seen from the other end. That is, whenever a symbol at position i changes, a symbol at position i + 1 passes through all possible symbols and creates a ripple effect until we reach the end. Since 0 and 1 do not have any characters associated with them. we must break down because there will be no iteration for these numbers.

Let's take the second approach, as it will be easy to implement with recursion. We go to the end and come back one after another. Great condition for recursion. allows you to search for the base register. When we get to the last character, we print the word with all possible characters for the last digit and return. Simple base register. When we get to the last character, we print the word with all possible characters for the last digit and return. Simple base case.

The following is an implementation of the C recursive approach for printing the entire possible word corresponding to an input number n digits. Please note that the input number is presented as an array to simplify the code.

 #include <stdio.h> #include <string.h> // hashTable[i] stores all characters that correspond to digit i in phone const char hashTable[10][5] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // A recursive function to print all possible words that can be obtained // by input number[] of size n. The output words are one by one stored // in output[] void printWordsUtil(int number[], int curr_digit, char output[], int n) { // Base case, if current output word is prepared int i; if (curr_digit == n) { printf("%s ", output); return ; } // Try all 3 possible characters for current digir in number[] // and recur for remaining digits for (i=0; i<strlen(hashTable[number[curr_digit]]); i++) { output[curr_digit] = hashTable[number[curr_digit]][i]; printWordsUtil(number, curr_digit+1, output, n); if (number[curr_digit] == 0 || number[curr_digit] == 1) return; } } // A wrapper over printWordsUtil(). It creates an output array and // calls printWordsUtil() void printWords(int number[], int n) { char result[n+1]; result[n] ='\0'; printWordsUtil(number, 0, result, n); } //Driver program int main(void) { int number[] = {2, 3, 4}; int n = sizeof(number)/sizeof(number[0]); printWords(number, n); return 0; } 

Output:

 adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi 

Time complexity:

The complexity of the time above the code is O (4 ^ n), where n is the number of digits in the input number.

Literature:

http://www.flipkart.com/programming-interviews-exposed-secrets-landing-your-next-job-3rd/p/itmdxghumef3sdjn?pid=9788126539116&affid=sandeepgfg

Answer 7

In javascript. The CustomCounter class takes care of increasing indexes. Then just print the various possible combinations.

 var CustomCounter = function(min, max) { this.min = min.slice(0) this.max = max.slice(0) this.curr = this.min.slice(0) this.length = this.min.length } CustomCounter.prototype.increment = function() { for (var i = this.length - 1, ii = 0; i >= ii; i--) { this.curr[i] += 1 if (this.curr[i] > this.max[i]) { this.curr[i] = 0 } else { break } } } CustomCounter.prototype.is_max = function() { for (var i = 0, ii = this.length; i < ii; ++i) { if (this.curr[i] !== this.max[i]) { return false } } return true } var PhoneNumber = function(phone_number) { this.phone_number = phone_number this.combinations = [] } PhoneNumber.number_to_combinations = { 1: ['1'] , 2: ['2', 'a', 'b', 'c'] , 3: ['3', 'd', 'e', 'f'] , 4: ['4', 'g', 'h', 'i'] , 5: ['5', 'j', 'k', 'l'] , 6: ['6', 'm', 'n', 'o'] , 7: ['7', 'p', 'q', 'r', 's'] , 8: ['8', 't', 'u', 'v'] , 9: ['9', 'w', 'x', 'y', 'z'] , 0: ['0', '+'] } PhoneNumber.prototype.get_combination_by_digit = function(digit) { return PhoneNumber.number_to_combinations[digit] } PhoneNumber.prototype.add_combination_by_indexes = function(indexes) { var combination = '' for (var i = 0, ii = indexes.length; i < ii; ++i) { var phone_number_digit = this.phone_number[i] combination += this.get_combination_by_digit(phone_number_digit)[indexes[i]] } this.combinations.push(combination) } PhoneNumber.prototype.update_combinations = function() { var min_indexes = [] , max_indexes = [] for (var i = 0, ii = this.phone_number.length; i < ii; ++i) { var digit = this.phone_number[i] min_indexes.push(0) max_indexes.push(this.get_combination_by_digit(digit).length - 1) } var c = new CustomCounter(min_indexes, max_indexes) while(true) { this.add_combination_by_indexes(c.curr) c.increment() if (c.is_max()) { this.add_combination_by_indexes(c.curr) break } } } var phone_number = new PhoneNumber('120') phone_number.update_combinations() console.log(phone_number.combinations) 

Answer 8

This task is similar to this leetcode problem. Here is the answer I posted for this problem on leetcode (check out github and video for an explanation).

So, the very first thing we need is some way to hold the mappings of a digit, and we can use the card to do this:

 private Map<Integer, String> getDigitMap() { return Stream.of( new AbstractMap.SimpleEntry<>(2, "abc"), new AbstractMap.SimpleEntry<>(3, "def"), new AbstractMap.SimpleEntry<>(4, "ghi"), new AbstractMap.SimpleEntry<>(5, "jkl"), new AbstractMap.SimpleEntry<>(6, "mno"), new AbstractMap.SimpleEntry<>(7, "pqrs"), new AbstractMap.SimpleEntry<>(8, "tuv"), new AbstractMap.SimpleEntry<>(9, "wxyz")) .collect(Collectors.toMap(AbstractMap.SimpleEntry::getKey, AbstractMap.SimpleEntry::getValue)); } 

The above method prepares a map, and the next method I would use is to provide a mapping for the provided digit:

 private String getDigitMappings(String strDigit, Map<Integer,String> digitMap) { int digit = Integer.valueOf(strDigit); return digitMap.containsKey(digit) ? digitMap.get(digit) : ""; } 

This problem can be solved by means of reverse tracking, and the solution for reverse tracking usually has a structure in which the signature of the method will contain: a container of results, temporary results, the source with the index, etc. Thus, the structure of the method will look like:

 private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) { // Condition to populate temp value to result // explore other arrangements based on the next input digit // Loop around the mappings of a digit and then to explore invoke the same method recursively // Also need to remove the digit which was in temp at last so as to get proper value in temp for next cycle in loop } 

And now the body of the method can be filled as (the result will be stored in a list, temp in a string builder, etc.)

 private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) { if(start >= digits.length()) { // condition result.add(temp.toString()); return; } String letters = getDigitMappings(digits.substring(start, start + 1), digitMap); // mappings of a digit to loop around for (int i = 0; i < letters.length(); i++) { temp.append(letters.charAt(i)); compute(result, temp, digits, start+1, digitMap); //explore for remaining digits temp.deleteCharAt(temp.length() - 1); // remove last in temp } } 

And finally, the method can be called as:

 public List<String> letterCombinations(String digits) { List<String> result = new ArrayList<>(); if(digits == null || digits.length() == 0) return result; compute(result, new StringBuilder(), digits, 0, getDigitMap()); return result; } 

Now the maximum matched characters for a digit can be 4 (for example, 9 has wxyz), and the reverse search includes an exhaustive search to examine all possible schemes (a state space tree), so for a digit of size n we will have 4x4x4....n times that is, the complexity will be O(4^n) .

Answer 9

 namespace WordsFromPhoneNumber { /// <summary> /// Summary description for WordsFromPhoneNumber /// </summary> [TestClass] public class WordsFromPhoneNumber { private static string[] Chars = { "0", "1", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ" }; public WordsFromPhoneNumber() { // // TODO: Add constructor logic here // } #region overhead private TestContext testContextInstance; /// <summary> ///Gets or sets the test context which provides ///information about and functionality for the current test run. ///</summary> public TestContext TestContext { get { return testContextInstance; } set { testContextInstance = value; } } #region Additional test attributes // // You can use the following additional attributes as you write your tests: // // Use ClassInitialize to run code before running the first test in the class // [ClassInitialize()] // public static void MyClassInitialize(TestContext testContext) { } // // Use ClassCleanup to run code after all tests in a class have run // [ClassCleanup()] // public static void MyClassCleanup() { } // // Use TestInitialize to run code before running each test // [TestInitialize()] // public void MyTestInitialize() { } // // Use TestCleanup to run code after each test has run // [TestCleanup()] // public void MyTestCleanup() { } // #endregion [TestMethod] public void TestMethod1() { IList<string> words = Words(new int[] { 2 }); Assert.IsNotNull(words, "null"); Assert.IsTrue(words.Count == 3, "count"); Assert.IsTrue(words[0] == "A", "a"); Assert.IsTrue(words[1] == "B", "b"); Assert.IsTrue(words[2] == "C", "c"); } [TestMethod] public void TestMethod23() { IList<string> words = Words(new int[] { 2 , 3}); Assert.IsNotNull(words, "null"); Assert.AreEqual(words.Count , 9, "count"); Assert.AreEqual(words[0] , "AD", "AD"); Assert.AreEqual(words[1] , "AE", "AE"); Assert.AreEqual(words[2] , "AF", "AF"); Assert.AreEqual(words[3] , "BD", "BD"); Assert.AreEqual(words[4] , "BE", "BE"); Assert.AreEqual(words[5] , "BF", "BF"); Assert.AreEqual(words[6] , "CD", "CD"); Assert.AreEqual(words[7] , "CE", "CE"); Assert.AreEqual(words[8] , "CF", "CF"); } [TestMethod] public void TestAll() { int[] number = new int [4]; Generate(number, 0); } private void Generate(int[] number, int index) { for (int x = 0; x <= 9; x += 3) { number[index] = x; if (index == number.Length - 1) { var w = Words(number); Assert.IsNotNull(w); foreach (var xx in number) { Console.Write(xx.ToString()); } Console.WriteLine(" possible words:\n"); foreach (var ww in w) { Console.Write("{0} ", ww); } Console.WriteLine("\n\n\n"); } else { Generate(number, index + 1); } } } #endregion private IList<string> Words(int[] number) { List<string> words = new List<string>(100); Assert.IsNotNull(number, "null"); Assert.IsTrue(number.Length > 0, "length"); StringBuilder word = new StringBuilder(number.Length); AddWords(number, 0, word, words); return words; } private void AddWords(int[] number, int index, StringBuilder word, List<string> words) { Assert.IsTrue(index < number.Length, "index < length"); Assert.IsTrue(number[index] >= 0, "number >= 0"); Assert.IsTrue(number[index] <= 9, "number <= 9"); foreach (var c in Chars[number[index]].ToCharArray()) { word.Append(c); if (index < number.Length - 1) { AddWords(number, index + 1, word, words); } else { words.Add(word.ToString()); } word.Length = word.Length - 1; } } } } 

Answer 10

Use the list L, where L [i] = the characters that the number i can represent.

L [1] = @,.,! (for example) L [2] = a, b, c

Etc.

Then you can do something like this (pseudo-C):

 void f(int k, int st[]) { if ( k > numberOfDigits ) { print contents of st[]; return; } for each character c in L[Digit At Position k] { st[k] = c; f(k + 1, st); } } 

Assuming each list contains 3 characters, we have 3 ^ 7 possibilities for 7 digits and 3 ^ 12 for 12, which is not so much. If you need all the combinations, I do not see a better way. You can avoid recursion and something else, but you won’t get something much faster than it doesn’t matter.

Answer 11

 public class Permutation { //display all combination attached to a 3 digit number public static void main(String ar[]){ char data[][]= new char[][]{{'a','k','u'}, {'b','l','v'}, {'c','m','w'}, {'d','n','x'}, {'e','o','y'}, {'f','p','z'}, {'g','q','0'}, {'h','r','0'}, {'i','s','0'}, {'j','t','0'}}; int num1, num2, num3=0; char tempdata[][]= new char[3][3]; StringBuilder number = new StringBuilder("324"); // a 3 digit number //copy data to a tempdata array------------------- num1= Integer.parseInt(number.substring(0,1)); tempdata[0] = data[num1]; num2= Integer.parseInt(number.substring(1,2)); tempdata[1] = data[num2]; num3= Integer.parseInt(number.substring(2,3)); tempdata[2] = data[num3]; //display all combinations-------------------- char temp2[][]=tempdata; char tempd, tempd2; int i,i2, i3=0; for(i=0;i<3;i++){ tempd = temp2[0][i]; for (i2=0;i2<3;i2++){ tempd2 = temp2[1][i2]; for(i3=0;i3<3;i3++){ System.out.print(tempd); System.out.print(tempd2); System.out.print(temp2[2][i3]); System.out.println(); }//for i3 }//for i2 } } }//end of class 

Answer 12

Here you will find the source (Scala) and work applet here.

Since 0 and 1 do not match characters, they build natural breakpoints in numbers. But they do not occur in every issue (except for 0 at the beginning). Longer digits, such as [phone], starting at 9 digits, can lead to OutOfMemoryErrors. Therefore, it would be better to divide the number into groups, for example

• 01723 5864
• 0172 35864

to see if you can understand the meaning of the shorter parts. I wrote such a program and checked some numbers from my friends, but rarely found combinations of shorter words that could be checked in the dictionary for comparison, not to mention single long words.

Therefore, my solution was to support the search , without full automation, displaying possible combinations, encouraging manual separation of the number, possibly several times.

So, I found + -RAD JUNG (+ -bycicle boy).

If you accept typos, abbreviations, foreign words, numbers like words, numbers in words and names, your chance to find a solution is much better than not messing around.

 246848 => 2hot4u (too hot for you) 466368 => goodn8 (good night) 1325 => 1FCK (Football club) 53517 => JDK17 (Java Developer Kit) 

- these are things that a person could observe - making an algorithm to find such things is quite difficult.

Answer 13

 #include <sstream> #include <map> #include <vector> map< int, string> keyMap; void MakeCombinations( string first, string joinThis , vector<string>& eachResult ) { if( !first.size() ) return; int length = joinThis.length(); vector<string> result; while( length ) { string each; char firstCharacter = first.at(0); each = firstCharacter; each += joinThis[length -1]; length--; result.push_back(each); } first = first.substr(1); vector<string>::iterator begin = result.begin(); vector<string>::iterator end = result.end(); while( begin != end) { eachResult.push_back( *begin); begin++; } return MakeCombinations( first, joinThis, eachResult); } void ProduceCombinations( int inNumber, vector<string>& result) { vector<string> inputUnits; int number = inNumber; while( number ) { int lastdigit ; lastdigit = number % 10; number = number/10; inputUnits.push_back( keyMap[lastdigit]); } if( inputUnits.size() == 2) { MakeCombinations(inputUnits[0], inputUnits[1], result); } else if ( inputUnits.size() > 2 ) { MakeCombinations( inputUnits[0] , inputUnits[1], result); vector<string>::iterator begin = inputUnits.begin(); vector<string>::iterator end = inputUnits.end(); begin += 2; while( begin != end ) { vector<string> intermediate = result; vector<string>::iterator ibegin = intermediate.begin(); vector<string>::iterator iend = intermediate.end(); while( ibegin != iend) { MakeCombinations( *ibegin , *begin, result); //resultbegin = ibegin++; } begin++; } } else { } return; } int _tmain(int argc, _TCHAR* argv[]) { keyMap[1] = ""; keyMap[2] = "abc"; keyMap[3] = "def"; keyMap[4] = "ghi"; keyMap[5] = "jkl"; keyMap[6] = "mno"; keyMap[7] = "pqrs"; keyMap[8] = "tuv"; keyMap[9] = "wxyz"; keyMap[0] = ""; string inputStr; getline(cin, inputStr); int number = 0; int length = inputStr.length(); int tens = 1; while( length ) { number += tens*(inputStr[length -1] - '0'); length--; tens *= 10; } vector<string> r; ProduceCombinations(number, r); cout << "[" ; vector<string>::iterator begin = r.begin(); vector<string>::iterator end = r.end(); while ( begin != end) { cout << *begin << "," ; begin++; } cout << "]" ; return 0; } 

Answer 14

The Python solution is quite economical, and since it uses generators, it is efficient in terms of memory usage.

 import itertools keys = dict(enumerate('::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ'.split(':'))) def words(number): digits = map(int, str(number)) for ls in itertools.product(*map(keys.get, digits)): yield ''.join(ls) for w in words(258): print w 

Obviously, itertools.product solves most of the problem for you. But writing is not difficult. Here you will find a solution in go that carefully repeats using the result array to generate all solutions in and closing f to capture the generated words. Combined, they provide O (log n) memory usage inside the product .

 package main import ( "bytes" "fmt" "strconv" ) func product(choices [][]byte, result []byte, i int, f func([]byte)) { if i == len(result) { f(result) return } for _, c := range choices[i] { result[i] = c product(choices, result, i+1, f) } } var keys = bytes.Split([]byte("::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ"), []byte(":")) func words(num int, f func([]byte)) { ch := [][]byte{} for _, b := range strconv.Itoa(num) { ch = append(ch, keys[b-'0']) } product(ch, make([]byte, len(ch)), 0, f) } func main() { words(256, func(b []byte) { fmt.Println(string(b)) }) } 

Answer 15

This is the C # port of this answer.

the code

 public class LetterCombinations { private static readonly Dictionary<string, string> Representations = new Dictionary<string, string> { {"2", "abc" }, {"3", "def" }, {"4", "ghi" }, {"5", "jkl" }, {"6", "mno" }, {"7", "pqrs" }, {"8", "tuv" }, {"9", "wxyz" }, }; public static List<string> FromPhoneNumber(string phoneNumber) { var result = new List<string> { string.Empty }; // go through each number in the phone for (int i = 0; i < phoneNumber.Length; i++) { var pre = new List<string>(); foreach (var str in result) { var letters = Representations[phoneNumber[i].ToString()]; // go through each representation of the number for (int j = 0; j < letters.Length; j++) { pre.Add(str + letters[j]); } } result = pre; } return result; } } 

Device tests

 public class UnitTest { [TestMethod] public void One_Digit_Yields_Three_Representations() { var sut = "2"; var expected = new List<string>{ "a", "b", "c" }; var actualResults = LetterCombinations.FromPhoneNumber(sut); CollectionAssert.AreEqual(expected, actualResults); } [TestMethod] public void Two_Digits_Yield_Nine_Representations() { var sut = "22"; var expected = new List<string> { "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc" }; var actualResults = LetterCombinations.FromPhoneNumber(sut); CollectionAssert.AreEqual(expected, actualResults); } [TestMethod] public void Three_Digits_Yield_ThirtyNine_Representations() { var sut = "222"; var actualResults = LetterCombinations.FromPhoneNumber(sut); var possibleCombinations = Math.Pow(3,3); //27 Assert.AreEqual(possibleCombinations, actualResults.Count); } } 

Answer 16

This version in C # is quite efficient and works for non-Western digits (for example, "1234567").

 static void Main(string[] args) { string phoneNumber = null; if (1 <= args.Length) phoneNumber = args[0]; if (string.IsNullOrEmpty(phoneNumber)) { Console.WriteLine("No phone number supplied."); return; } else { Console.WriteLine("Alphabetic phone numbers for \"{0}\":", phoneNumber); foreach (string phoneNumberText in GetPhoneNumberCombos(phoneNumber)) Console.Write("{0}\t", phoneNumberText); } } public static IEnumerable<string> GetPhoneNumberCombos(string phoneNumber) { phoneNumber = RemoveNondigits(phoneNumber); if (string.IsNullOrEmpty(phoneNumber)) return new List<string>(); char[] combo = new char[phoneNumber.Length]; return GetRemainingPhoneNumberCombos(phoneNumber, combo, 0); } private static string RemoveNondigits(string phoneNumber) { if (phoneNumber == null) return null; StringBuilder sb = new StringBuilder(); foreach (char nextChar in phoneNumber) if (char.IsDigit(nextChar)) sb.Append(nextChar); return sb.ToString(); } private static IEnumerable<string> GetRemainingPhoneNumberCombos(string phoneNumber, char[] combo, int nextDigitIndex) { if (combo.Length - 1 == nextDigitIndex) { foreach (char nextLetter in phoneNumberAlphaMapping[(int)char.GetNumericValue(phoneNumber[nextDigitIndex])]) { combo[nextDigitIndex] = nextLetter; yield return new string(combo); } } else { foreach (char nextLetter in phoneNumberAlphaMapping[(int)char.GetNumericValue(phoneNumber[nextDigitIndex])]) { combo[nextDigitIndex] = nextLetter; foreach (string result in GetRemainingPhoneNumberCombos(phoneNumber, combo, nextDigitIndex + 1)) yield return result; } } } private static char[][] phoneNumberAlphaMapping = new char[][] { new char[] { '0' }, new char[] { '1' }, new char[] { 'a', 'b', 'c' }, new char[] { 'd', 'e', 'f' }, new char[] { 'g', 'h', 'i' }, new char[] { 'j', 'k', 'l' }, new char[] { 'm', 'n', 'o' }, new char[] { 'p', 'q', 'r', 's' }, new char[] { 't', 'u', 'v' }, new char[] { 'w', 'x', 'y', 'z' } }; 

Answer 17

Oracle SQL: .

 CREATE TABLE digit_character_map (digit number(1), character varchar2(1)); SELECT replace(permutations,' ','') AS permutations FROM (SELECT sys_connect_by_path(map.CHARACTER,' ') AS permutations, LEVEL AS lvl FROM digit_character_map map START WITH map.digit = substr('12345',1,1) CONNECT BY digit = substr('12345',LEVEL,1)) WHERE lvl = length('12345'); 

Answer 18

C. ( , ). .

• ,

, ( ). , , .

 #include <stdlib.h> #include <stdio.h> #define CHARACTER_RANGE 95 // The range of valid password characters #define CHARACTER_OFFSET 32 // The offset of the first valid character void main(int argc, char *argv[], char *env[]) { int i; long int string; long int worker; char *guess; // Current Generation guess = (char*)malloc(1); // Allocate it so free doesn't fail int cur; for ( string = 0; ; string++ ) { worker = string; free(guess); guess = (char*)malloc((string/CHARACTER_RANGE+1)*sizeof(char)); // Alocate for the number of characters we will need for ( i = 0; worker > 0 && i < string/CHARACTER_RANGE + 1; i++ ) // Work out the string { cur = worker % CHARACTER_RANGE; // Take off the last digit worker = (worker - cur) / CHARACTER_RANGE; // Advance the digits cur += CHARACTER_OFFSET; guess[i] = cur; } guess[i+1] = '\0'; // NULL terminate our string printf("%s\t%d\n", guess, string); } } 

Answer 19

 static final String[] keypad = {"", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"}; String[] printAlphabet(int num){ if (num >= 0 && num < 10){ String[] retStr; if (num == 0 || num ==1){ retStr = new String[]{""}; } else { retStr = new String[keypad[num].length()]; for (int i = 0 ; i < keypad[num].length(); i++){ retStr[i] = String.valueOf(keypad[num].charAt(i)); } } return retStr; } String[] nxtStr = printAlphabet(num/10); int digit = num % 10; String[] curStr = null; if(digit == 0 || digit == 1){ curStr = new String[]{""}; } else { curStr = new String[keypad[digit].length()]; for (int i = 0; i < keypad[digit].length(); i++){ curStr[i] = String.valueOf(keypad[digit].charAt(i)); } } String[] result = new String[curStr.length * nxtStr.length]; int k=0; for (String cStr : curStr){ for (String nStr : nxtStr){ result[k++] = nStr + cStr; } } return result; } 

Answer 20

 /** * Simple Java implementation without any input/error checking * (expects all digits as input) **/ public class PhoneSpeller { private static final char[][] _letters = new char[][]{ {'0'}, {'1'}, {'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'I'}, {'J', 'K', 'L'}, {'M', 'N', 'O'}, {'P', 'Q', 'R', 'S'}, {'T', 'U', 'V'}, {'W', 'X', 'Y', 'Z'} }; public static void main(String[] args) { if (args.length != 1) { System.out.println("Please run again with your phone number (no dashes)"); System.exit(0); } recursive_phoneSpell(args[0], 0, new ArrayList<String>()); } private static void recursive_phoneSpell(String arg, int index, List<String> results) { if (index == arg.length()) { printResults(results); return; } int num = Integer.parseInt(arg.charAt(index)+""); if (index==0) { for (int j = 0; j<_letters[num].length; j++) { results.add(_letters[num][j]+""); } recursive_phoneSpell(arg, index+1, results); } else { List<String> combos = new ArrayList<String>(); for (int j = 0; j<_letters[num].length; j++) { for (String result : results) { combos.add(result+_letters[num][j]); } } recursive_phoneSpell(arg, index+1, combos); } } private static void printResults(List<String> results) { for (String result : results) { System.out.println(result); } } } 

Answer 21

, , , , .

, . , factorial (7) = 5040 . (12) ~ = 4 * 10 ^ 8, .

. Looping , "Next Permutation".

, {0, 1, 2, 3, 4, 5} , , . 0 = A, 5 = F

. , 1,3,5,4 1,4,3,5

.

• . 3

• , 3, . four

• . 1,4,5,3 1,4,3,5

( ), , , 1000 , . . 4 , 10 ^ 9 = 1 !.

Answer 22

.. , .... , , .....

, ....

 import java.util.ArrayList; public class phonenumbers { /** * @param args */ public static String mappings[][] = { {"0"}, {"1"}, {"A", "B", "C"}, {"D", "E", "F"}, {"G", "H", "I"}, {"J", "K", "L"}, {"M", "N", "O"}, {"P", "Q", "R", "S"}, {"T", "U", "V"}, {"W", "X", "Y", "Z"} }; public static void main(String[] args) { // TODO Auto-generated method stub String phone = "3333456789"; ArrayList<String> list= generateAllnums(phone,"",0); } private static ArrayList<String> generateAllnums(String phone,String sofar,int j) { // TODO Auto-generated method stub //System.out.println(phone); if(phone.isEmpty()){ System.out.println(sofar); for(int k1=0;k1<sofar.length();k1++){ int m=sofar.toLowerCase().charAt(k1)-48; if(m==-16) continue; int i=k1; while(true && i<sofar.length()-2){ if(sofar.charAt(i+1)==' ') break; else if(sofar.charAt(i+1)==sofar.charAt(k1)){ i++; }else{ break; } } i=i-k1; //System.out.print(" " + m +", " + i + " "); System.out.print(mappings[m][i%3]); k1=k1+i; } System.out.println(); return null; } int num= phone.charAt(j); int k=0; for(int i=j+1;i<phone.length();i++){ if(phone.charAt(i)==num){ k++; } } if(k!=0){ int p=0; ArrayList<String> list2= generateAllnums(phone.substring(p+1), sofar+phone.charAt(p)+ " ", 0); ArrayList<String> list3= generateAllnums(phone.substring(p+1), sofar+phone.charAt(p), 0); } else{ ArrayList<String> list1= generateAllnums(phone.substring(1), sofar+phone.charAt(0), 0); } return null; } } 

Answer 23

++ 11.

 #include <iostream> #include <array> #include <list> std::array<std::string, 10> pm = { "0", "1", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ" }; void generate_mnemonic(const std::string& numbers, size_t i, std::string& m, std::list<std::string>& mnemonics) { // Base case if (numbers.size() == i) { mnemonics.push_back(m); return; } for (char c : pm[numbers[i] - '0']) { m[i] = c; generate_mnemonic(numbers, i + 1, m, mnemonics); } } std::list<std::string> phone_number_mnemonics(const std::string& numbers) { std::list<std::string> mnemonics; std::string m(numbers.size(), 0); generate_mnemonic(numbers, 0, m, mnemonics); return mnemonics; } int main() { std::list<std::string> result = phone_number_mnemonics("2276696"); for (const std::string& s : result) { std::cout << s << std::endl; } return 0; } 

Answer 24

( ), C Java . 0 1 ( 0 1), , 555-5055, .

There he is. .

 public static void printPhoneWords(int[] number) { char[] output = new char[number.length]; printWordsUtil(number,0,output); } static String[] phoneKeys= new String[]{"0", "1", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"}; private static void printWordsUtil(int[] number, int curDigIndex, char[] output) { // Base case, if current output word is done if (curDigIndex == output.length) { System.out.print(String.valueOf(output) + " "); return; } // Try all 3-4 possible characters for the current digit in number[] // and recurse for the remaining digits char curPhoneKey[] = phoneKeys[number[curDigIndex]].toCharArray(); for (int i = 0; i< curPhoneKey.length ; i++) { output[curDigIndex] = curPhoneKey[i]; printWordsUtil(number, curDigIndex+1, output); if (number[curDigIndex] <= 1) // for 0 or 1 return; } } public static void main(String[] args) { int number[] = {2, 3, 4}; printPhoneWords(number); System.out.println(); } 

Answer 25

  private List<string> strs = new List<string>(); char[] numbersArray; private int End = 0; private int numberOfStrings; private void PrintLetters(string numbers) { this.End = numbers.Length; this.numbersArray = numbers.ToCharArray(); this.PrintAllCombinations(this.GetCharacters(this.numbersArray[0]), string.Empty, 0); } private void PrintAllCombinations(char[] letters, string output, int depth) { depth++; for (int i = 0; i < letters.Length; i++) { if (depth != this.End) { output += letters[i]; this.PrintAllCombinations(this.GetCharacters(Convert.ToChar(this.numbersArray[depth])), output, depth); output = output.Substring(0, output.Length - 1); } else { Console.WriteLine(output + letters[i] + (++numberOfStrings)); } } } private char[] GetCharacters(char x) { char[] arr; switch (x) { case '0': arr = new char[1] { '.' }; return arr; case '1': arr = new char[1] { '.' }; return arr; case '2': arr = new char[3] { 'a', 'b', 'c' }; return arr; case '3': arr = new char[3] { 'd', 'e', 'f' }; return arr; case '4': arr = new char[3] { 'g', 'h', 'i' }; return arr; case '5': arr = new char[3] { 'j', 'k', 'l' }; return arr; case '6': arr = new char[3] { 'm', 'n', 'o' }; return arr; case '7': arr = new char[4] { 'p', 'q', 'r', 's' }; return arr; case '8': arr = new char[3] { 't', 'u', 'v' }; return arr; case '9': arr = new char[4] { 'w', 'x', 'y', 'z' }; return arr; default: return null; } } 

Answer 26

, . , . 120 , 40 .

 private List<String> generateWords(String phoneNumber) { List<String> words = new LinkedList<String>(); List<String> wordsCache = new LinkedList<String>(); this.generatePossibleWords("", phoneNumber, words, wordsCache); return words; } private void generatePossibleWords(String prefix, String remainder, List<String> words, List<String> wordsCache) { int index = Integer.parseInt(remainder.substring(0, 1)); for (int i = 0; i < phoneKeyMapper.get(index).size(); i++) { String mappedChar = phoneKeyMapper.get(index).get(i); if (prefix.equals("") && !wordsCache.isEmpty()) { for (String word : wordsCache) { words.add(mappedChar + word); } } else { if (remainder.length() == 1) { String stringToBeAdded = prefix + mappedChar; words.add(stringToBeAdded); wordsCache.add(stringToBeAdded.substring(1)); LOGGER.finest("adding stringToBeAdded = " + stringToBeAdded.substring(1)); } else { generatePossibleWords(prefix + mappedChar, remainder.substring(1), words, wordsCache); } } } } private void createPhoneNumberMapper() { if (phoneKeyMapper == null) { phoneKeyMapper = new ArrayList<>(); phoneKeyMapper.add(0, new ArrayList<String>()); phoneKeyMapper.add(1, new ArrayList<String>()); phoneKeyMapper.add(2, new ArrayList<String>()); phoneKeyMapper.get(2).add("A"); phoneKeyMapper.get(2).add("B"); phoneKeyMapper.get(2).add("C"); phoneKeyMapper.add(3, new ArrayList<String>()); phoneKeyMapper.get(3).add("D"); phoneKeyMapper.get(3).add("E"); phoneKeyMapper.get(3).add("F"); phoneKeyMapper.add(4, new ArrayList<String>()); phoneKeyMapper.get(4).add("G"); phoneKeyMapper.get(4).add("H"); phoneKeyMapper.get(4).add("I"); phoneKeyMapper.add(5, new ArrayList<String>()); phoneKeyMapper.get(5).add("J"); phoneKeyMapper.get(5).add("K"); phoneKeyMapper.get(5).add("L"); phoneKeyMapper.add(6, new ArrayList<String>()); phoneKeyMapper.get(6).add("M"); phoneKeyMapper.get(6).add("N"); phoneKeyMapper.get(6).add("O"); phoneKeyMapper.add(7, new ArrayList<String>()); phoneKeyMapper.get(7).add("P"); phoneKeyMapper.get(7).add("Q"); phoneKeyMapper.get(7).add("R"); phoneKeyMapper.get(7).add("S"); phoneKeyMapper.add(8, new ArrayList<String>()); phoneKeyMapper.get(8).add("T"); phoneKeyMapper.get(8).add("U"); phoneKeyMapper.get(8).add("V"); phoneKeyMapper.add(9, new ArrayList<String>()); phoneKeyMapper.get(9).add("W"); phoneKeyMapper.get(9).add("X"); phoneKeyMapper.get(9).add("Y"); phoneKeyMapper.get(9).add("Z"); } } 

Answer 27

Objective-C:

 - (NSArray *)lettersForNumber:(NSNumber *)number { switch ([number intValue]) { case 2: return @[@"A",@"B",@"C"]; case 3: return @[@"D",@"E",@"F"]; case 4: return @[@"G",@"H",@"I"]; case 5: return @[@"J",@"K",@"L"]; case 6: return @[@"M",@"N",@"O"]; case 7: return @[@"P",@"Q",@"R",@"S"]; case 8: return @[@"T",@"U",@"V"]; case 9: return @[@"W",@"X",@"Y",@"Z"]; default: return nil; } } - (NSArray *)letterCombinationsForNumbers:(NSArray *)numbers { NSMutableArray *combinations = [[NSMutableArray alloc] initWithObjects:@"", nil]; for (NSNumber *number in numbers) { NSArray *lettersNumber = [self lettersForNumber:number]; //Ignore numbers that don't have associated letters if (lettersNumber.count == 0) { continue; } NSMutableArray *currentCombinations = [combinations mutableCopy]; combinations = [[NSMutableArray alloc] init]; for (NSString *letter in lettersNumber) { for (NSString *letterInResult in currentCombinations) { NSString *newString = [NSString stringWithFormat:@"%@%@", letterInResult, letter]; [combinations addObject:newString]; } } } return combinations; } 

code>

Answer 28

, , , O (?) , , Ruby Array.product. What do you think?

EDIT: Python , ,

 def phone_to_abc(phone) phone_abc = [ '0', '1', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz' ] phone_map = phone.chars.map { |x| phone_abc[x.to_i].chars } result = phone_map[0] for i in 1..phone_map.size-1 result = result.product(phone_map[i]) end result.each { |x| puts "#{x.join}" } end phone_to_abc('86352') 

Answer 29

R :

 # Create phone pad two <- c("A", "B", "C") three <- c("D", "E", "F") four <- c("G", "H", "I") five <- c("J", "K", "L") six <- c("M", "N", "O", "P") seven <- c("Q", "R", "S") eight <- c("T", "U", "V") nine <- c("W", "X", "Y", "Z") # Choose three numbers number_1 <- two number_2 <- three number_3 <- six # create an object to save the combinations to combinations <- NULL # Loop through the letters in number_1 for(i in number_1){ # Loop through the letters in number_2 for(j in number_2){ # Loop through the letters in number_3 for(k in number_3){ # Add each of the letters to the combinations object combinations <- c(combinations, paste0(i, j, k)) } } } # Print all of the possible combinations combinations 

, R, .

Answer 30

R , .

1 ( Unix 100 000 ), 100 0,1 :

 library(data.table) #example dictionary dict.orig = tolower(readLines("/usr/share/dict/american-english")) #split each word into its constituent letters #words shorter than the longest padded with "" for simpler retrieval dictDT = setDT(tstrsplit(dict.orig, split = "", fill = "")) #lookup table for conversion #NB: the following are found in the dictionary and would need # to be handled separately -- ignoring here # (accents should just be appended to # matches for unaccented version): # c("", "'", "á", "â", "å", "ä", # "ç", "é", "è", "ê", "í", "ñ", # "ó", "ô", "ö", "û", "ü") lookup = data.table(num = c(rep('2', 3), rep('3', 3), rep('4', 3), rep('5', 3), rep('6', 3), rep('7', 4), rep('8', 3), rep('9', 4)), let = letters) #using the lookup table, convert to numeric for (col in names(dictDT)) { dictDT[lookup, (col) := i.num, on = setNames("let", col)] } #back to character vector dict.num = do.call(paste0, dictDT) #sort both for faster vector search idx = order(dict.num) dict.num = dict.num[idx] dict.orig = dict.orig[idx] possibilities = function(input) dict.orig[dict.num == input] #sample output: possibilities('269') # [1] "amy" "bmw" "cox" "coy" "any" "bow" "box" "boy" "cow" "cox" "coy" possibilities('22737') # [1] "acres" "bards" "barer" "bares" "barfs" "baser" "bases" "caper" # [9] "capes" "cards" "cares" "cases"