Как я могу распечатать все возможные сочетания букв, которые может представить данный номер телефона?

Используйте список 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 символа, у нас есть 3 ^ 7 вариантов для 7 цифр и 3 ^ 12 для 12, что не так уж и много. Если вам нужны все комбинации, я не вижу лучшего способа. Вы можете избежать рекурсии и прочего, но вы не получите чего-то намного быстрее, несмотря ни на что.

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

Очевидным решением является функция сопоставления цифры со списком ключей, а затем функция, которая будет генерировать возможные комбинации:

Первое очевидно, второе более проблематично, потому что у вас есть около 3 ^ number комбинаций цифр, которых может быть очень большое количество.

Один из способов сделать это - рассмотреть каждую возможность сопоставления цифр как цифру в числе (на основе 4) и реализовать что-то близкое к счетчику (перепрыгивая через некоторые экземпляры, поскольку обычно отображается менее 4 букв. до цифры).

Более очевидными решениями могут быть вложенные циклы или рекурсия, которые менее элегантны, но, на мой взгляд, действительны.

Еще одна вещь, о которой следует позаботиться, - это избегать проблем с масштабируемостью (например, сохранение возможностей в памяти и т. Д.), Поскольку мы говорим о множестве комбинаций.

P.S. Еще одно интересное продолжение вопроса - это локализация.

Эта версия на C # достаточно эффективна и работает с незападными цифрами (например, "۱۲۳۴۵۶۷").

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

На 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);
        }
    }
}

В 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 каждой комбинацией существующего префикса и возможной буквы.

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