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

Ответ 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 - список результатов; сначала он заполняется одним элементом, пустой строкой. Затем для каждого символа во входной строке он просматривает список букв, которые соответствуют ему из dict, определенного в верхней части. Затем он заменяет список ret каждой комбинацией существующего префикса и возможной буквы.

Ответ 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-значные международные номера влияют на дизайн.

Изменение: Международные номера также будут обрабатываться

Ответ 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);
        }
    }
}

Ответ 4

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

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

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

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

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

P.S. Еще одним интересным продолжением вопроса будет локализация.

Ответ 5

В С++ (рекурсивный):

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

Эта функция может быть вызвана с 'k' и 'i' равными нулю.

Любой, кто требует больше иллюстраций для понимания логики, может объединить метод рекурсии со следующим выходом:

ADG
ADH
ADI

AEG
AEH
AEI

AFG
AFH
AFI


BDG
BDH
BDI

BEG
BEH
BEI

BFG
BFH
...

Ответ 6

В числовых клавиатурах тексты и цифры помещаются на один и тот же ключ. Например, у 2 есть "ABC", если мы хотим написать что-нибудь, начиная с "A", мы должны ввести ключ 2 один раз. Если бы мы хотели набрать "B", нажмите клавишу 2 два раза и три раза для ввода "C. ниже изображена такая клавиатура.

клавиатура http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard.png

С учетом клавиатуры, как показано на диаграмме, и числа из n цифр, перечислите все слова, которые возможны, нажав эти цифры.

Например, если входной номер равен 234, возможные слова, которые могут быть сформированы (в алфавитном порядке): adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi

Сначала сделаем некоторые вычисления. Сколько слов возможно с семью цифрами с каждой цифрой, представляющей n букв? Для первой цифры у нас есть не более четырех вариантов, и для каждого выбора для первой буквы у нас есть не более четырех вариантов для второй цифры и так далее. Поэтому его простой математикой будет O (4 ^ n). Поскольку ключи 0 и 1 не имеют соответствующего алфавита, и многие символы имеют 3 символа, 4 ^ n будет верхней границей числа слов, а не минимальными словами.

Теперь давайте сделаем несколько примеров.

Для числа выше 234. Вы видите какой-либо шаблон? Да, мы замечаем, что последний символ всегда либо G, H или I, и всякий раз, когда он сбрасывает свое значение от я до G, цифра слева от него изменяется. Аналогично, когда второй последний алфавит сбрасывает свое значение, третий последний алфавит получает изменения и так далее. Первый символ сбрасывается только один раз, когда мы сгенерировали все слова. Это можно посмотреть и с другого конца. То есть всякий раз, когда меняется символ в позиции i, символ в позиции я + 1 проходит через все возможные символы и создает эффект пульсации, пока мы не достигнем конца. Поскольку 0 и 1 не имеют никаких связанных с ними символов. мы должны сломаться, поскольку для этих цифр не будет итерации.

Давайте возьмем второй подход, поскольку его будет легко реализовать с помощью рекурсии. Мы идем до конца и возвращаемся один за другим. Отличное условие для рекурсии. позволяет искать базовый регистр. Когда мы дойдем до последнего символа, мы печатаем слово со всеми возможными символами для последней цифры и возвращаем. Простой базовый регистр. Когда мы дойдем до последнего символа, мы печатаем слово со всеми возможными символами для последней цифры и возвращаем. Простой базовый корпус.

Ниже приводится реализация C рекурсивного подхода для печати всего возможного слова, соответствующего номеру ввода n цифр. Обратите внимание, что номер ввода представлен как массив для упрощения кода.

#include <stdio.h>
#include <string.h>

// hashTable[i] stores all characters that correspond to digit i in phone
const char hashTable[10][5] = {"", "", "abc", "def", "ghi", "jkl",
                           "mno", "pqrs", "tuv", "wxyz"};

// A recursive function to print all possible words that can be obtained
// by input number[] of size n.  The output words are one by one stored
// in output[]
void  printWordsUtil(int number[], int curr_digit, char output[], int n)
{
    // Base case, if current output word is prepared
int i;
if (curr_digit == n)
{
    printf("%s ", output);
    return ;
}

// Try all 3 possible characters for current digir in number[]
// and recur for remaining digits
for (i=0; i<strlen(hashTable[number[curr_digit]]); i++)
{
    output[curr_digit] = hashTable[number[curr_digit]][i];
    printWordsUtil(number, curr_digit+1, output, n);
    if (number[curr_digit] == 0 || number[curr_digit] == 1)
        return;
}
}

// A wrapper over printWordsUtil().  It creates an output array and
// calls printWordsUtil()
void printWords(int number[], int n)
{
char result[n+1];
result[n] ='\0';
printWordsUtil(number, 0, result, n);
}

//Driver program
int main(void)
{
int number[] = {2, 3, 4};
int n = sizeof(number)/sizeof(number[0]);
printWords(number, n);
return 0;
}

Вывод:

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

Сложность времени:

Сложность времени выше кода равна O (4 ^ n), где n - количество цифр во входном номере.

Литература:

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

Ответ 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)

Ответ 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
}

И теперь тело метода может быть заполнено как (результат будет сохранен в списке, temp в строителе строк и т.д.)

private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) {
        if(start >= digits.length()) { // condition
            result.add(temp.toString());
            return;
        }

        String letters = getDigitMappings(digits.substring(start, start + 1), digitMap); // mappings of a digit to loop around
        for (int i = 0; i < letters.length(); i++) {
            temp.append(letters.charAt(i));
            compute(result, temp, digits, start+1, digitMap); //explore for remaining digits
            temp.deleteCharAt(temp.length() - 1); // remove last in temp
        }
}

И, наконец, метод может быть вызван как:

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

Теперь максимальные сопоставленные символы для цифры могут быть 4 (например, 9 имеет wxyz), а обратный поиск включает в себя исчерпывающий поиск, чтобы исследовать все возможные схемы (дерево пространства состояний), поэтому для цифры размера n у нас будет 4x4x4....n times то есть сложность будет O(4^n).

Ответ 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;
            }
        }
    }
}

Ответ 10

Используйте список L, где L [i] = символы, которые цифра я может представлять.

L [1] = @,.,! (например) L [2] = a, b, c

Etc.

Затем вы можете сделать что-то вроде этого (псевдо-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, чего не так много. Если вам нужны все комбинации, я не вижу лучшего способа. Вы можете избежать рекурсии и еще чего-то, но вы не получите что-то намного быстрее, чем это не важно.

Ответ 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

Ответ 12

Здесь вы найдете источник (Scala) и рабочий апплет здесь.

Так как 0 и 1 не соответствуют символам, они строят естественные точки останова в числах. Но они не встречаются в каждом номере (кроме 0 в начале). Более длинные цифры, такие как +49567892345, начиная с 9 цифр, могут привести к OutOfMemoryErrors. Поэтому было бы лучше разбить число на группы, например

• 01723 5864
• 0172 35864

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

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

Итак, я нашел + -RAD JUNG (+ -bycicle boy).

Если вы принимаете опечатки, аббревиатуры, иностранные слова, цифры как слова, цифры в словах и именах, ваш шанс найти решение намного лучше, чем без возиться.

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

- это вещи, которые человек мог бы наблюдать - сделать алгоритм найти такие вещи довольно сложно.

Ответ 13

#include <sstream>
#include <map>
#include <vector>

map< int, string> keyMap;

void MakeCombinations( string first, string joinThis , vector<string>& eachResult )
{
    if( !first.size() )
        return;

    int length = joinThis.length();
    vector<string> result;

    while( length )
    {
        string each;
        char firstCharacter = first.at(0);
        each =  firstCharacter;
        each += joinThis[length -1];
        length--;

        result.push_back(each);     
    }

    first = first.substr(1);

    vector<string>::iterator begin = result.begin();    
    vector<string>::iterator end = result.end();
    while( begin != end)
    {
        eachResult.push_back( *begin);
        begin++;
    }

    return MakeCombinations( first, joinThis, eachResult);
}


void ProduceCombinations( int inNumber, vector<string>& result)
{
    vector<string> inputUnits;

    int number = inNumber;
    while( number )
    {
        int lastdigit ;

        lastdigit = number % 10;
        number = number/10;
        inputUnits.push_back( keyMap[lastdigit]);
    }

    if( inputUnits.size() == 2)
    {
        MakeCombinations(inputUnits[0], inputUnits[1], result);
    }
    else if ( inputUnits.size() > 2 )
    {
        MakeCombinations( inputUnits[0] , inputUnits[1], result);

        vector<string>::iterator begin = inputUnits.begin();    
        vector<string>::iterator end = inputUnits.end();

        begin += 2;
        while(  begin != end )
        {
            vector<string> intermediate = result;
            vector<string>::iterator ibegin = intermediate.begin(); 
            vector<string>::iterator iend = intermediate.end(); 

            while( ibegin != iend)
            {
                MakeCombinations( *ibegin , *begin, result);
                //resultbegin =  
                ibegin++; 
            }
            begin++;            
        }
    }
    else
    {

    }

    return;
}

int _tmain(int argc, _TCHAR* argv[])
{
    keyMap[1] = "";
    keyMap[2] = "abc";
    keyMap[3] = "def";
    keyMap[4] = "ghi";
    keyMap[5] = "jkl";
    keyMap[6] = "mno";
    keyMap[7] = "pqrs";
    keyMap[8] = "tuv";
    keyMap[9] = "wxyz";
    keyMap[0] = "";

    string  inputStr;
    getline(cin, inputStr);

    int number = 0;

    int length = inputStr.length();

    int tens = 1;
    while( length )
    {
        number += tens*(inputStr[length -1] - '0');
        length--;
        tens *= 10;
    }

    vector<string> r;
    ProduceCombinations(number, r);

    cout << "[" ;

    vector<string>::iterator begin = r.begin(); 
    vector<string>::iterator end = r.end();

    while ( begin != end)
    {
        cout << *begin << "," ;
        begin++;
    }

    cout << "]" ;

    return 0;
}

Ответ 14

Решение 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 для генерации всех решений in и закрытия f для захвата сгенерированных слов. В сочетании, они обеспечивают использование памяти O (log n) внутри product.

package main

import (
    "bytes"
    "fmt"
    "strconv"
)

func product(choices [][]byte, result []byte, i int, f func([]byte)) {
    if i == len(result) {
        f(result)
        return
    }
    for _, c := range choices[i] {
        result[i] = c
        product(choices, result, i+1, f)
    }
}

var keys = bytes.Split([]byte("::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ"), []byte(":"))

func words(num int, f func([]byte)) {
    ch := [][]byte{}
    for _, b := range strconv.Itoa(num) {
        ch = append(ch, keys[b-'0'])
    }
    product(ch, make([]byte, len(ch)), 0, f)
}

func main() {
    words(256, func(b []byte) { fmt.Println(string(b)) })
}

Ответ 15

Это порт С# этого ответа.

код

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

Ответ 16

Эта версия на С# достаточно эффективна и работает для незападных цифр (например, "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' }
};

Ответ 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');

Ответ 18

Вот один для боли C. Этот человек не эффективен (на самом деле я не думаю, что он вообще есть). Но есть некоторые интересные моменты.

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

Хорошо, что нет никакого реального ограничения на размер строки (без ограничения символа). Это позволяет вам генерировать более длинные и длинные строки, если нужно, просто ожидая.

#include <stdlib.h>
#include <stdio.h>

#define CHARACTER_RANGE 95  //  The range of valid password characters
#define CHARACTER_OFFSET 32 //  The offset of the first valid character

void main(int argc, char *argv[], char *env[])
{
    int i;

    long int string;
    long int worker;
    char *guess;    //  Current Generation
    guess = (char*)malloc(1);   //  Allocate it so free doesn't fail

    int cur;

    for ( string = 0; ; string++ )
    {
        worker = string;

        free(guess);
        guess = (char*)malloc((string/CHARACTER_RANGE+1)*sizeof(char)); //  Alocate for the number of characters we will need

        for ( i = 0; worker > 0 && i < string/CHARACTER_RANGE + 1; i++ )    //  Work out the string
        {
            cur = worker % CHARACTER_RANGE; //  Take off the last digit
            worker = (worker - cur) / CHARACTER_RANGE;  //  Advance the digits
            cur += CHARACTER_OFFSET;

            guess[i] = cur;
        }
        guess[i+1] = '\0';  //  NULL terminate our string

        printf("%s\t%d\n", guess, string);
    }
}

Ответ 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;
    }

Ответ 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);
        }
    }
}

Ответ 21

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

Прежде всего, мы изучаем сложность пространства и времени. Что действительно плохо, так как это факториал поэтому для factorial (7) = 5040 любой рекурсивный алгоритм будет делать. Но для факториала (12) ~ = 4 * 10 ^ 8, что может вызвать переполнение стека в рекурсивном решении.

Поэтому я бы не стал рекурсивным алгоритмом. Решение Looping очень прямолинейно, используя "Next Permutation".

Итак, я бы создал и создал массив {0, 1, 2, 3, 4, 5} и сгенерировал всю перестановку, и при печати замените их соответствующими символами, например. 0 = A, 5 = F

Далее Пермский алгоритм работает следующим образом. Например, с учетом 1,3,5,4 следующая перестановка составляет 1,4,3,5

Шаги для поиска следующей переменной.

• Справа налево найдите первое уменьшающееся число. например 3

• Слева направо найдите наименьшее число, большее 3, например. 4

• Поменяйте эти числа как обратное подмножество. 1,4,5,3 обратное подмножество 1,4,3,5

Используя следующую перестановку (или поворот), вы генерируете определенное подмножество перестановок, скажем, вы хотите показать 1000 перестановок, начиная с определенного номера телефона. Это может избавить вас от наличия всех номеров в памяти. Если я сохраняю числа как 4 байтовых целых числа, 10 ^ 9 байтов = 1 ГБ!.

Ответ 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;

    }

}

Ответ 23

Это рекурсивный алгоритм в С++ 11.

#include <iostream>
#include <array>
#include <list>

std::array<std::string, 10> pm = {
    "0", "1", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"
};

void generate_mnemonic(const std::string& numbers, size_t i, std::string& m,
    std::list<std::string>& mnemonics)
{
    // Base case
    if (numbers.size() == i) {
        mnemonics.push_back(m);
        return;
    }

    for (char c : pm[numbers[i] - '0']) {
        m[i] = c;
        generate_mnemonic(numbers, i + 1, m, mnemonics);
    }
}

std::list<std::string> phone_number_mnemonics(const std::string& numbers)
{
    std::list<std::string> mnemonics;
    std::string m(numbers.size(), 0);
    generate_mnemonic(numbers, 0, m, mnemonics);
    return mnemonics;
}

int main() {
    std::list<std::string> result = phone_number_mnemonics("2276696");
    for (const std::string& s : result) {
        std::cout << s << std::endl;
    }
    return 0;
}

Ответ 24

Я переписал последний ответ на этот вопрос (указанный выше), от 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();
}

Ответ 25

    private List<string> strs = new List<string>();        
    char[] numbersArray;
    private int End = 0;
    private int numberOfStrings;

    private void PrintLetters(string numbers)
    {
        this.End = numbers.Length;
        this.numbersArray = numbers.ToCharArray();
        this.PrintAllCombinations(this.GetCharacters(this.numbersArray[0]), string.Empty, 0);
    }

    private void PrintAllCombinations(char[] letters, string output, int depth)
    {
        depth++;
        for (int i = 0; i < letters.Length; i++)
        {
            if (depth != this.End)
            {
                output += letters[i];
                this.PrintAllCombinations(this.GetCharacters(Convert.ToChar(this.numbersArray[depth])), output, depth);
                output = output.Substring(0, output.Length - 1);
            }
            else
            {
                Console.WriteLine(output + letters[i] + (++numberOfStrings));
            }
        }
    }

    private char[] GetCharacters(char x)
    {
        char[] arr;
        switch (x)
        {
            case '0': arr = new char[1] { '.' };
                return arr;
            case '1': arr = new char[1] { '.' };
                return arr;
            case '2': arr = new char[3] { 'a', 'b', 'c' };
                return arr;
            case '3': arr = new char[3] { 'd', 'e', 'f' };
                return arr;
            case '4': arr = new char[3] { 'g', 'h', 'i' };
                return arr;
            case '5': arr = new char[3] { 'j', 'k', 'l' };
                return arr;
            case '6': arr = new char[3] { 'm', 'n', 'o' };
                return arr;
            case '7': arr = new char[4] { 'p', 'q', 'r', 's' };
                return arr;
            case '8': arr = new char[3] { 't', 'u', 'v' };
                return arr;
            case '9': arr = new char[4] { 'w', 'x', 'y', 'z' };
                return arr;
            default: return null;
        }
    }

Ответ 26

Я реализовал кеш, который помог уменьшить количество рекурсий. Этот кеш не позволит сканировать буквы, которые он уже сделал для предыдущих комбинаций. Для одного случая это было для циклов 120 КБ, после реализации кэша это было уменьшено до 40 КБ.

private List<String> generateWords(String phoneNumber) {

    List<String> words = new LinkedList<String>();
    List<String> wordsCache = new LinkedList<String>();

    this.generatePossibleWords("", phoneNumber, words, wordsCache);

    return words;
}

private void generatePossibleWords(String prefix, String remainder,
    List<String> words, List<String> wordsCache) {

    int index = Integer.parseInt(remainder.substring(0, 1));

    for (int i = 0; i < phoneKeyMapper.get(index).size(); i++) {

        String mappedChar = phoneKeyMapper.get(index).get(i);

        if (prefix.equals("") && !wordsCache.isEmpty()) {

            for (String word : wordsCache) {
                words.add(mappedChar + word);
            }
        } else {

            if (remainder.length() == 1) {
                String stringToBeAdded = prefix + mappedChar;
                words.add(stringToBeAdded);
                wordsCache.add(stringToBeAdded.substring(1));
                LOGGER.finest("adding stringToBeAdded = " + stringToBeAdded.substring(1));

            } else {
                generatePossibleWords(prefix + mappedChar,
                remainder.substring(1), words, wordsCache);
            }
        }
    }
}

private void createPhoneNumberMapper() {

    if (phoneKeyMapper == null) {

    phoneKeyMapper = new ArrayList<>();
    phoneKeyMapper.add(0, new ArrayList<String>());
    phoneKeyMapper.add(1, new ArrayList<String>());

    phoneKeyMapper.add(2, new ArrayList<String>());
    phoneKeyMapper.get(2).add("A");
    phoneKeyMapper.get(2).add("B");
    phoneKeyMapper.get(2).add("C");

    phoneKeyMapper.add(3, new ArrayList<String>());
    phoneKeyMapper.get(3).add("D");
    phoneKeyMapper.get(3).add("E");
    phoneKeyMapper.get(3).add("F");

    phoneKeyMapper.add(4, new ArrayList<String>());
    phoneKeyMapper.get(4).add("G");
    phoneKeyMapper.get(4).add("H");
    phoneKeyMapper.get(4).add("I");

    phoneKeyMapper.add(5, new ArrayList<String>());
    phoneKeyMapper.get(5).add("J");
    phoneKeyMapper.get(5).add("K");
    phoneKeyMapper.get(5).add("L");

    phoneKeyMapper.add(6, new ArrayList<String>());
    phoneKeyMapper.get(6).add("M");
    phoneKeyMapper.get(6).add("N");
    phoneKeyMapper.get(6).add("O");

    phoneKeyMapper.add(7, new ArrayList<String>());
    phoneKeyMapper.get(7).add("P");
    phoneKeyMapper.get(7).add("Q");
    phoneKeyMapper.get(7).add("R");
    phoneKeyMapper.get(7).add("S");

    phoneKeyMapper.add(8, new ArrayList<String>());
    phoneKeyMapper.get(8).add("T");
    phoneKeyMapper.get(8).add("U");
    phoneKeyMapper.get(8).add("V");

    phoneKeyMapper.add(9, new ArrayList<String>());
    phoneKeyMapper.get(9).add("W");
    phoneKeyMapper.get(9).add("X");
    phoneKeyMapper.get(9).add("Y");
    phoneKeyMapper.get(9).add("Z");
    }
}

Ответ 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;
}

Ответ 28

Я попробовал его в рубине и придумал другой способ сделать это, вероятно, неэффективен, как время и пространство O (?) на данный момент, но мне это нравится, потому что он использует встроенный Ruby метод Array.product. Как вы думаете?

EDIT: я вижу очень похожее решение в Python выше, но я не видел его, когда добавлял свой ответ

def phone_to_abc(phone)

  phone_abc = [
    '0', '1', 'abc', 'def', 'ghi',
    'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'
  ]

  phone_map = phone.chars.map { |x| phone_abc[x.to_i].chars }
  result = phone_map[0]
  for i in 1..phone_map.size-1
    result = result.product(phone_map[i])
  end
  result.each { |x|
    puts "#{x.join}"
  }

end

phone_to_abc('86352')

Ответ 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, использующее больше циклов и выборку в моем блоге.

Ответ 30

Этот подход использует R и основан на первом преобразовании словаря в соответствующее цифровое представление, а затем используя это как просмотр.

Преобразование занимает только 1 секунду на моей машине (преобразование из родного словаря Unix около 100 000 слов), а типичный поиск до 100 различных цифровых входов занимает в общей сложности 0,1 секунды:

library(data.table)
#example dictionary
dict.orig = tolower(readLines("/usr/share/dict/american-english"))

#split each word into its constituent letters
#words shorter than the longest padded with "" for simpler retrieval
dictDT = setDT(tstrsplit(dict.orig, split = "", fill = ""))

#lookup table for conversion
#NB: the following are found in the dictionary and would need
#  to be handled separately -- ignoring here
#  (accents should just be appended to
#   matches for unaccented version):
#      c("", "'", "á", "â", "å", "ä",
#        "ç", "é", "è", "ê", "í", "ñ",
#        "ó", "ô", "ö", "û", "ü")
lookup = data.table(num = c(rep('2', 3), rep('3', 3), rep('4', 3),
                            rep('5', 3), rep('6', 3), rep('7', 4),
                            rep('8', 3), rep('9', 4)),
                    let = letters)

#using the lookup table, convert to numeric
for (col in names(dictDT)) {
  dictDT[lookup, (col) := i.num, on = setNames("let", col)]
}

#back to character vector
dict.num = do.call(paste0, dictDT)

#sort both for faster vector search
idx = order(dict.num)
dict.num = dict.num[idx]
dict.orig = dict.orig[idx]

possibilities = function(input) dict.orig[dict.num == input]

#sample output:
possibilities('269')
# [1] "amy" "bmw" "cox" "coy" "any" "bow" "box" "boy" "cow" "cox" "coy"
possibilities('22737')
# [1] "acres" "bards" "barer" "bares" "barfs" "baser" "bases" "caper"
# [9] "capes" "cards" "cares" "cases"