我刚试过第一次编程访谈，其中一个问题是编写了一个给出7位数电话号码的程序，可以打印每个号码可能代表的所有可能的字母组合。
问题的第二部分就是如果这是一个12位数的国际号码呢？这会对你的设计产生什么影响。
我没有在采访中写的代码，但我得到的印象是他对此不满意。 做这个的最好方式是什么？
在Python中，迭代：
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是迄今为止的结果清单;最初它填充了一个项目，空字符串。然后，对于输入字符串中的每个字符，它会从顶部定义的字典中查找与其匹配的字母列表。然后它将列表ret替换为现有前缀和可能字母的每个组合。
使用列表L，其中L [i] =数字i可以表示的符号。
L [1] = @，。，！ （例如）L [2] = a，b，c
等等。
然后你可以做这样的事情（伪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);
}
}
假设每个列表包含3个字符，我们对7个数字有3 ^ 7个可能性，12个有3 ^ 12个，这不是很多。如果你需要所有组合，我看不到更好的方法。你可以避免递归和诸如此类的东西，但无论如何你都不会比这更快。
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
You find source (Scala) here和an working applet here.
由于0和1与字符不匹配，因此它们在数字中构建自然断点。但它们不会出现在每个数字中（开头的0除外）。从9位数字开始，更长的数字如+49567892345，可能会导致OutOfMemoryErrors。所以最好将一个数字分成像这样的组
如果从较短的部分可以理解的话，看看。我写了这样一个程序，并测试了我的朋友的一些数字，但很少发现较短的单词组合，可以在字典中检查匹配，更不用说单个，长单词。
所以我的决定是只支持搜索，没有完全自动化，通过显示可能的组合，鼓励手动分割数量，也许多次。
所以我找到了+ -RAD JUNG（+ -bycicle boy）。
如果你接受拼写错误，缩写，外来词，数字作为单词，单词中的数字和名称，你找到解决方案的机会要好得多，而不是摆弄。
246848 => 2hot4u (too hot for you)
466368 => goodn8 (good night)
1325 => 1FCK (Football club)
53517 => JDK17 (Java Developer Kit)
是人类可能观察到的事情 - 让算法发现这样的事情是相当困难的。
#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;
}
Python解决方案非常经济，因为它使用生成器在内存使用方面是高效的。
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
显然itertools.product正在为您解决大部分问题。但是写自己并不困难。这是一个go中的解决方案，小心重复使用数组result生成所有解决方案，并使用闭包f来捕获生成的单词。结合起来，这些可以在product中使用O（log n）内存。
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)) })
}
这是this答案的C＃端口。
码
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;
}
}
单元测试
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);
}
}
C＃中的这个版本效率很高，适用于非西方数字（例如“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' }
};
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');
这是痛苦的一个。这个可能效率不高（实际上我根本不认为它）。但它有一些有趣的方面。
对此有好处的是字符串的大小没有实际限制（没有字符限制）这允许您生成更长和更长的字符串，如果需要只是等待。
#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);
}
}
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;
}
它类似于一个名为letter combinations of a phone number的问题，这是我的解决方案。 它适用于任意数量的数字，只要结果不超过内存限制即可。
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', "");
}} ;
}
我不确定12位数的国际数字如何影响设计。
编辑：国际号码也将被处理
/**
* 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);
}
}
}
我是一个新手，所以无论我错在哪里都请纠正我。
首先是调查时空复杂性。这是非常糟糕的，因为它是阶乘的，因此对于factorial（7）= 5040，任何递归算法都会这样做。但是对于阶乘（12）〜= 4 * 10 ^ 8，这可能导致递归解决方案中的堆栈溢出。
所以我不会尝试递归算法。循环解决方案使用“Next Permutation”非常直接。
所以我会创建和数组{0,1,2,3,4,5}并生成所有排列，而打印时用相应的字符替换它们，例如。 0 = A，5 = F.
下一个Perm算法的工作原理如下。例如，给定1,3,5,4下一个排列是1,4,3,5
寻找下一个烫发的步骤。
使用下一个排列（或旋转），您可以生成特定的排列子集，例如，您希望从特定电话号码开始显示1000个排列。这可以避免让你在内存中拥有所有数字。如果我将数字存储为4字节整数，则10 ^ 9字节= 1 GB！
这是相同的工作代码..它的每一步的递归检查一系列中相同数字出现的每个组合的可能性....我不确定是否有更好的解决方案然后这从复杂性的角度来看.....
如有任何问题，请告诉我....
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;
}
}
这是C ++ 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;
}
我重写了这个（referred above）的最新答案，从C到Java。我还包括对0和1（作为0和1）的支持，因为555-5055之类的数字与上述代码完全不兼容。
这里是。一些评论被保留。
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();
}
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;
}
}
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;
}
我在ruby中尝试了它，并提出了一种不同的做法，它可能效率不高，就像时间和空间O（？），但我喜欢它，因为它使用Ruby的内置Array.product方法。你怎么看？
编辑：我在上面看到了一个非常类似的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')
使用嵌套循环的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解决方案，使用更多循环和采样on my blog。
这种方法使用R并且基于首先将字典转换为其对应的数字表示，然后将其用作查找。
转换只需要1秒钟在我的机器上（从大约100,000字的原生Unix字典转换），典型的查找最多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"
在Java中使用递归：
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);
}
}
}
规模解决方案
def mnemonics(phoneNum: String, dict: IndexedSeq[String]): Iterable[String] = {
def mnemonics(d: Int, prefix: String): Seq[String] = {
if (d >= phoneNum.length) {
Seq(prefix)
} else {
for {
ch <- dict(phoneNum.charAt(d).asDigit)
num <- mnemonics(d + 1, s"$prefix$ch")
} yield num
}
}
mnemonics(0, "")
}
假设每个数字映射到最多4个字符，递归调用T的数量满足不等式T(n) <= 4T(n-1)，其为4^n的顺序。
显而易见的解决方案是将数字映射到键列表，然后生成可能组合的函数：
第一个是显而易见的，第二个更有问题，因为你有大约3 ^个数字组合，这可能是一个非常大的数字。
一种方法是将数字匹配的每种可能性看作数字中的数字（在基数4上）并实现接近计数器的某些东西（跳过某些实例，因为通常少于4个字母可映射到数字）。
更明显的解决方案是嵌套循环或递归，它们都不太优雅，但在我看来是有效的。
必须注意的另一件事是避免可扩展性问题（例如，将可能性保留在内存中等），因为我们正在讨论许多组合。
附：问题的另一个有趣的扩展是本地化。
在C ++中（递归）：
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;
}
}
可以使用'k'和'i'等于零来调用此函数。
任何需要更多插图来理解逻辑的人都可以将递归技术与以下输出结合起来：
ADG
ADH
ADI
AEG
AEH
AEI
AFG
AFH
AFI
BDG
BDH
BDI
BEG
BEH
BEI
BFG
BFH
...
在数字键盘中，文本和数字放在同一个键上。例如，如果我们想要写一些以'A'开头的东西，我们需要输入一次键2，那么2有“ABC”。如果我们想输入'B'，按键2两次，然后输入'C'三次。下面是这种键盘的图片。
keypad http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard.png
给定图中所示的键盘和n位数字，按下这些数字列出所有可能的单词。
例如，如果输入数字是234，则可以形成的可能单词是（按字母顺序排列）：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
我们先做一些计算吧。七位数可能有多少个单词，每个数字代表n个字母？对于第一个数字，我们最多有四个选项，对于第一个字母的每个选项，我们最多有四个选择第二个数字，依此类推。所以这是简单的数学，它将是O（4 ^ n）。由于键0和1没有任何相应的字母表，并且许多字符具有3个字符，因此4 ^ n将是单词数量的上限而不是最小单词。
现在让我们举一些例子。
对于234以上的数字。你看到任何模式？是的，我们注意到最后一个字符总是G，H或I，每当它将其值从I重置为G时，它左边的数字就会改变。类似地，每当第二个最后一个字母表重置其值时，第三个最后一个字母表将获得更改，依此类推当我们生成所有单词时，第一个字符只重置一次。这也可以从另一端看。也就是说，无论何时位置i处的角色发生变化，位置i + 1处的角色都会经历所有可能的角色，并且它会产生连锁反应，直到我们到达终点。由于0和1没有任何与之关联的字符。我们应该打破，因为这些数字不会迭代。
让我们采用第二种方法，因为使用递归很容易实现它。我们一直走到最后，一个接一个地回来。递归的完美条件。让我们搜索基本案例。当我们到达最后一个字符时，我们打印带有最后一个数字的所有可能字符的单词并返回。简单的基本情况。当我们到达最后一个字符时，我们打印带有最后一个数字的所有可能字符的单词并返回。简单的基础案例。
以下是C实现的递归方法，以打印对应于n位输入数字的所有可能的字。请注意，输入数字表示为数组以简化代码。
#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;
}
输出：
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
时间复杂性：
上述代码的时间复杂度为O（4 ^ n），其中n是输入数字的位数。
参考文献：
在JavaScript中。 CustomCounter类负责递增索引。然后输出不同的可能组合。
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)
这个问题类似于this leetcode问题。以下是我为leetcode提交此问题的答案（请查看github和video进行说明）。
所以我们需要的第一件事是保持数字映射的一些方法，我们可以使用地图：
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));
}
上面的方法是准备地图，我将使用的下一个方法是提供所提供数字的映射：
private String getDigitMappings(String strDigit, Map<Integer,String> digitMap) {
int digit = Integer.valueOf(strDigit);
return digitMap.containsKey(digit) ? digitMap.get(digit) : "";
}
这个问题可以使用回溯来解决，回溯解决方案通常具有方法签名将包含的结构：结果容器，临时结果，带索引的原始源等。因此方法结构将具有以下形式：
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
}
现在可以填充方法体（结果将保存在列表中，temp在字符串构建器中等）
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
}
}
最后，该方法可以调用为：
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;
}
现在一个数字的最大映射字符可以是4（例如9有wxyz），回溯涉及穷举搜索以探索所有可能的安排（状态空间树）所以对于大小n的数字我们将有4x4x4....n times，即复杂性将是O(4^n) 。
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;
}
}
}
}