如何打印给定电话号码可以代表的所有可能的字母组合？

Question

我刚刚尝试进行我的第一次编程面试，其中一个问题是编写一个程序，给定一个 7 位数字的电话号码，可以打印每个数字可以代表的所有可能的字母组合。

问题的第二部分是如果这是一个 12 位国际号码怎么办？这将如何影响您的设计。

我没有在采访中编写的代码，但我的印象是他对此不满意。
最好的方法是什么？

Answer 1

在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。

Answer 2

它类似于电话号码的字母组合,
这是我的解决方案。
它适用于任意数量的数字，只要结果不超过内存限制即可。

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 位国际号码如何影响设计。

编辑：国际号码也将得到处理

Answer 3

在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);
        }
    }
}

Answer 4

显而易见的解决方案是将数字映射到键列表的函数，然后是生成可能组合的函数：

第一个很明显，第二个更成问题，因为您有大约 3^ 个数字组合，这可以是一个非常大的数字。

一种方法是将数字匹配为数字中的数字（以 4 为基数）的每种可能性，并实现一些接近计数器的东西（跳过某些实例，因为通常可映射到数字的字母少于 4 个） ）。

更明显的解决方案是嵌套循环或递归，它们都不太优雅，但在我看来是有效的。

必须注意的另一件事是避免可扩展性问题（例如，将可能性保留在内存中等），因为我们正在讨论很多组合。

PS 这个问题的另一个有趣的延伸是本地化。

Answer 5

在 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”等于 0 来调用该函数。

任何需要更多插图来理解逻辑的人都可以将递归技术与以下输出结合起来：

ADG
ADH
ADI

AEG
AEH
AEI

AFG
AFH
AFI


BDG
BDH
BDI

BEG
BEH
BEI

BFG
BFH
...

Answer 6

在数字键盘中，文本和数字位于同一个键上。例如，2 有“ABC”，如果我们想写入以“A”开头的任何内容，我们需要输入键 2 一次。如果我们想输入“B”，请按 2 键两次并三次以输入“C”。下面是此类键盘的图片。

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

给定如图所示的键盘和一个数字，列出按这些数字可能出现的所有单词。

例如，如果输入数字是 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 实现，用于打印与数字输入数字对应的所有可能的单词。请注意，输入数字表示为数组以简化代码。

#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 是输入数字的位数。

参考文献：

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

Answer 7

在 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)

Answer 8

这个问题类似于这个leetcode问题。这是我针对这个问题提交给leetcode的答案（检查 github 和视频了解说明）。

因此，我们需要的第一件事是某种方法来保存数字的映射，我们可以为此使用映射：

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
}

现在可以填充方法主体as（结果将保存在列表中，临时保存在字符串生成器等中）

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 次，即复杂度为 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

使用列表 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 种可能性，这是没有那么多。如果您需要所有组合，我看不出更好的方法。你可以避免递归之类的东西，但无论如何你都不会得到比这更快的东西。

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

#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 13

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)) })
}

Answer 14

这是这个答案的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);
    }
}

Answer 15

Python 解决方案

def keypad_words(number):
    
    num_pad_dict = {
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z'],
    }
    result = num_pad_dict.get(number[0], '')
    for i in range(1,len(number)):
        letters = num_pad_dict.get(number[i], '')
        new_result = []
        for prefix in result:  
            for letter in letters:
                new_result.append(prefix+letter)   
            
        result = new_result
    return result
    return []

Answer 16

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' }
};

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 的方法。这个方法似乎无效（事实上我认为根本无效）。但它有一些有趣的方面。

1. 它需要一个数字并将其转换为字符串
2. 它每次只增加一次种子编号以创建下一个连续字符串

这样做的好处是字符串的大小没有真正的限制（没有字符限制）这允许您如果需要，只需等待即可生成越来越长的字符串。

#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

我是个新手，所以有错误的地方请指正。

第一件事是研究太空和时间复杂度。这真的很糟糕，因为它是阶乘
因此对于阶乘(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

查找下一个排列的步骤。

1. 从右到左，找到第一个递减的数字。例如3

2. 从左到右，找到大于 3 的最小数字，例如。 4

3. 交换这些数字作为反转子集。 1,4,5,3 反转子集 1,4,3,5

使用下一个排列（或旋转），您可以生成特定的排列子集，假设您要显示从特定电话号码开始的 1000 个排列。这可以帮助您避免将所有数字都存储在内存中。如果我将数字存储为 4 字节整数，则 10^9 字节 = 1 GB！。

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

您可以在此处找到源代码 (Scala) 和 此处是一个工作小程序。

由于 0 和 1 与字符不匹配，因此它们在数字中构建自然断点。但它们并不出现在每个数字中（开头的 0 除外）。较长的数字（例如从 9 位数字开始的 +49567892345）可能会导致 OutOfMemoryErrors。因此，最好将数字分成

• 01723 5864
• 0172 35864

等组，看看是否可以从较短的部分中理解。我写了一个这样的程序，并测试了朋友提供的一些数字，但很少发现短单词的组合，可以在字典中查找匹配，更不用说单个长单词了。

因此，我的决定是仅支持搜索，不支持完全自动化，通过显示可能的组合，鼓励手动拆分数字，也许可以多次。

所以我找到了+-RAD JUNG（+-自行车男孩）。

如果你接受拼写错误、缩写、外来词、数字作为单词、数字作为单词和名称，那么你找到解决方案的机会比不乱搞要好得多。

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

是人类可能观察到的东西——让算法找到这样的东西是相当困难的。

Answer 24

这是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;
}

Answer 25

我重写了对此的最新答案（上面提到的），从 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();
}

Answer 26

    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 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;
}

Answer 28

我在 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')

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 秒（从大约 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"