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

Question

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

Вторая часть вопроса была похожа на то, что, если бы это был 12-значный международный номер? Как это повлияет на ваш дизайн.

У меня нет кода, который я написал в интервью, но у меня сложилось впечатление, что он не был доволен им.
Каков наилучший способ сделать это?

Answer 1

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

Answer 2

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 3

Решение 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 решает большую часть проблемы для вас. Но написать это самому не сложно. Вот решение на ходу, которое осторожно, чтобы повторно использовать массив result для генерации всех решений и закрытие 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)) })
}

Answer 4

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

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

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

• 01723 5864
• 0172 35864

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

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

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

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

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

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

Answer 6

Вот один для боли 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 7

Один вариант в Objective-C:

</p>

<pre><code>- (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 8

Я реализовал кеш, который помог уменьшить количество рекурсий. Этот кеш не позволит сканировать буквы, которые он уже сделал для предыдущих комбинаций. Для одного случая это было для циклов 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");
    }
}

Answer 9

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 10

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