我怎样才能打印出给定的电话号码可以代表的所有可能的字母组合？
我刚刚尝试了我的第一次编程面试，其中一个问题是编写一个给定7位数字电话号码的程序，可以打印每个数字可能表示的所有可能的字母组合。
问题的第二部分是如果这是一个12位数字的国际号码呢？ 这将如何影响你的devise。
我没有我在面试中写的代码，但是我觉得他并不满意。
做这个的最好方式是什么？
在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是到目前为止的结果列表; 最初它是填充一个项目，空string。 然后，对于inputstring中的每个字符，它从顶部定义的字典中查找匹配它的字母列表。 然后用现有前缀和可能的字母的每个组合replace列表ret 。
它类似于一个电话号码组合的问题，这里是我的解决scheme。
它适用于任意数量的数字，只要结果不超过内存限制。
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++){ for(String str: res) String letters = map.get(digits.charAt(i)); 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('2',"abc"); put('3',"def"); put('4',"ghi"); put('5',"jkl"); put('6',"mno"); put('7',"pqrs"); put('8',"tuv"); put('9',"wxyz"); }} ; }
我不确定12位国际号码如何影响devise。
显而易见的解决scheme是将数字映射到键列表的function，然后是可以生成可能的组合的function：
第一个是显而易见的，第二个是更有问题的，因为你有大约3 ^数字组合，这可能是一个非常大的数字。
一种方法是将数字匹配的每种可能性看作一个数字中的一个数字（基数为4），并实现一些与计数器接近的东西（跳过一些实例，因为通常less于4个字母可映射到一个数字）。
更明显的解决scheme将是嵌套循环或recursion，这是不够优雅的，但在我看来是有效的。
另一件需要注意的事情是避免可扩展性问题（例如保持内存中的可能性等），因为我们正在讨论大量的组合。
PS问题的另一个有趣的扩展将是本地化。
在Java中使用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); } } }
在C ++（recursion）中：
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'等于零来调用。
任何需要更多插图来理解逻辑的人都可以将recursion技术与以下输出结合起来：
ADG ADH ADI AEG AEH AEI AFG AFH AFI BDG BDH BDI BEG BEH BEI BFG BFH ...
在数字键盘中，文本和数字放在同一个键上。 例如，如果我们想写任何以“A”开始的东西，我们需要键入一次键2，那么就有“ABC”。 如果我们想input'B'，按键2两次，三次input'C'。 下面是这种键盘的图片。
键盘http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard.png
给出如图所示的键盘和一个数字号码，按下这些数字列出所有可能的单词。
例如，如果input数字是234，可以形成的可能的词是（按字母顺序）：adg adh adi aeg aeh aei afg afh afh bdg bdh bdi beg beh bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi
我们先做一些计算。 有七个数字，每个数字代表n个字母，可能有多less个单词？ 对于第一个数字，我们至多有四个select，对于第一个字母的每个select，对于第二个数字我们最多有四个select，依此类推。 所以这是简单的math将是O（4 ^ n）。 由于密钥0和1没有任何相应的字母表，许多字符有3个字符，所以4 ^ n是字数的上限，而不是最小字数。
现在我们来做一些例子。
对于234以上的数字。你看到任何模式？ 是的，我们注意到最后一个字符总是G，H或I，并且每当它从I重置为G时，它左边的数字都会被改变。 同样，每当第二个字母表重置其值，第三个字母表得到更改等等。 当我们产生了所有的单词时，第一个字符只能重置一次。 这也可以从另一端看。 也就是说，当位置i的字符改变时，位置i + 1处的字符会遍历所有可能的字符，并创造出连续的效果，直到达到最后。 由于0和1没有任何关联的字符。 我们应该打破，因为没有这些数字的迭代。
让我们采取第二种方法，因为使用recursion很容易实现它。 我们走到最后一个一个回来。 recursion的完美条件。 让我们search基础案例。 当我们到达最后一个字符时，我们用最后一个数字的所有可能的字符打印这个单词并返回。 简单的基本情况。当我们到达最后一个字符时，我们打印所有可能的字符为最后一个数字并返回。 简单的基本情况。
下面是C实现recursion方法来打印对应于一个数字input号的所有可能的单词。 请注意，input号码被表示为一个数组来简化代码。
#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是input数字的位数。
参考文献：
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; } } } }
使用列表L其中L [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，这并不是很多。 如果你需要所有的组合，我没有看到更好的方法。 你可以避免recursion和什么，但不pipe怎么样，你都不会得到比这更快的东西。
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
你在这里find源代码（Scala）和一个可用的applet。
由于0和1与字符不匹配，因此它们会build立数量上的自然断点。 但是它们并不是每个数字都出现的（开始时除了0）。 更长的数字，例如从9位开始的+49567892345，可能会导致OutOfMemoryErrors。 所以最好将一个数字分成几组
- 01723 5864
- 0172 35864
看看，如果你能从短的部分理解。 我写了这样一个程序，并且testing了一些来自我的朋友的数字，但很less发现较短单词的组合，这可以在字典中进行匹配检查，更不用说单个长单词了。
所以我的决定只是通过显示可能的组合来支持search ，没有完全的自动化，鼓励分手，也许多次。
所以我find了+ -RJ JUNG（+ -Acicle boy）。
如果你接受拼写错误，缩写，外来词，数字作为单词，数字和名字，你find解决scheme的机会比没有摆弄的好得多。
246848 => 2hot4u (too hot for you) 466368 => goodn8 (good night) 1325 => 1FCK (Football club) 53517 => JDK17 (Java Developer Kit)
是人类可能观察到的事情 – 使algorithm发现这样的事情是相当困难的。
#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; }
在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)
Python解决scheme非常经济，因为它使用生成器在内存使用方面效率很高。
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中的一个解决scheme，它仔细地重新使用数组result来生成所有的解决scheme，并使用闭包f来捕获生成的单词。 结合起来，这些给产品内的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)) }) }
这是这个答案的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; } }
unit testing
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');
这是一个疼痛C.这是一个likley没有效率（实际上我不认为它是根本）。 但是它有一些有趣的方面。
- 它需要一个数字并将其转换为一个string
- 它每次只提升一次种子编号，创build下一个连续的string
这样做的好处是对string的大小没有实际的限制（没有字符限制）。如果需要等待，可以生成更长和更长的string。
#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; }
/** * 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); } } }
我是一个新手，所以请纠正我，无论我错了。
首先是考虑到空间和时间的复杂性。 这是非常糟糕的，因为它是阶乘，所以任何recursionalgorithm都可以用阶乘（7）= 5040。 但是在recursion解决scheme中可能导致堆栈溢出的阶乘（12）〜= 4 * 10 ^ 8。
所以我不会尝试recursionalgorithm。 使用“Next Permutation”，循环解决scheme非常简单。
所以我会创build和数组{0，1，2，3，4，5}并生成所有排列，并在打印时将其replace为相应的字符，例如。 0 = A，5 = F
Next Permalgorithm的工作原理如下。 例如给定1,3,5,4下一个排列是1,4,3,5
寻找下一个烫发的步骤。
-
从右到左find第一个递减的数字。 例如3
-
从左到右，find大于3的最小数字。 4
-
将这些数字交换为相反的子集。 1,4,5,3反向子集1,4,3,5
使用下一个排列（或旋转），您可以生成特定的排列子集，例如，您想要显示从特定电话号码开始的1000个排列。 这可以节省你在内存中的所有数字。 如果我将数字存储为4个字节的整数，则10 ^ 9个字节= 1 GB！
下面是相同的工作代码..它的recursion每个步骤检查每个组合中出现同一个数字在一系列的可能性….我不知道是否有任何更好的解决scheme，那么这从复杂的angular度…..
请让我知道任何问题….
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中的recursionalgorithm。
#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; }
Here is a good and simple java implementation:
I rewrote the latest answer to this ( referred above ) , from C to Java . I also included the support for 0 and 1 (as 0 and 1) because numbers such as 555-5055 weren't working at all with the above code.
这里是。 Some comments are preserved.
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; } }
I've implemented a cache which helped to reduce number of recursions. This cache will avoid scanning of letters that it had already done for previous combinations. For one instance it was going for 120k loops, after cache implementation it got reduced to 40k.
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"); } }
One option in 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; }
I tried it in ruby, and came up with a different way of doing, it's probably not efficient, like time and space O(?) at this point, but I like it because it uses Ruby's builtin Array.product method. 你怎么看？
EDIT: I see a very similar solution in Python above, but I hadn't seen it when I added my answer
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')
An R solution using nested loops:
# 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
I posted another, more bizarre R solution using more loops and sampling on my blog .
This approach uses R and is based on first converting the dictionary to its corresponding digit representation, then using this as a look-up.
The conversion only takes 1 second on my machine (converting from the native Unix dictionary of about 100,000 words), and typical look-ups of up to 100 different digit inputs take a total of .1 seconds:
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"
;){kind=link}