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

Question

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

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

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

Answer 1

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

Я попробовал это в 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 3

Этот подход использует 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"

Answer 4

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 5

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

Пожалуйста, дайте мне знать по любым вопросам ....

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 6

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

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

Так что я бы не стал использовать рекурсивный алгоритм. Циклическое решение очень простое, используя «Следующая перестановка».

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

Алгоритм Next 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 ГБ!.

Answer 7

Решение 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 8

/**
 * 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 9

Решение Scala:

def mnemonics(phoneNum: String, dict: IndexedSeq[String]): Iterable[String] = {
  def mnemonics(d: Int, prefix: String): Seq[String] = {
    if (d >= phoneNum.length) {
      Seq(prefix)
    } else {
      for {
        ch <- dict(phoneNum.charAt(d).asDigit)
        num <- mnemonics(d + 1, s"$prefix$ch")
      } yield num
    }
  }

  mnemonics(0, "")
}

Предполагая, что каждая цифра соответствует максимум 4 символам, число рекурсивных вызовов T удовлетворяет неравенству T(n) <= 4T(n-1), которое имеет порядок 4^n.

Answer 10

Это рекурсивный алгоритм в 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;
}