logo标签列表

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

algorithmlanguage-agnosticcombinatorics
63

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

第二部分问题类似于如果这是一个12位的国际号码，那么它将如何影响您的设计。

我没有在面试中编写的代码，但我有印象他对此不满意。
这样做的最佳方法是什么？

2
你能否给出你解决这个问题的方法的概要？ - GSto
你是用递归还是迭代的方式实现的？如果你最初的方法不是递归，那么很可能更难推广到任意数量的数字（解释后续问题）。 - Tyler McHenry
@Tyler，最初我是用迭代的方式做的，但建议我也可以用递归的方式做。 - Salaban
请使用Java 8检查我的答案：https://dev59.com/N3E95IYBdhLWcg3wXcrd#54499782，以及视频：https://www.youtube.com/watch?v=3_Kx8ChYOFk，以获取更多解释。时间复杂度将为O(4^n)。 - akhil_mittal
34个回答
47
在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。

6
美丽。它的问题是，如果数字“1”存在，它将返回 ['']。为了解决这个问题，请使用 digit_map.get(char,char)。作为奖励，如果有连字符存在，它们将保持原样。 - redtuna
因此，没有包括数字1的单词编号，因为1上没有字母。但是，包括数字是有意义的 - 并且可以通过将数字附加到返回字符集来更整洁地处理。 - Nick Johnson
我认为你错过了 letters = digit_map.get(char, '') 如果 letters == '': 继续 ret = [prefix + letter for prefix in ret for letter in letters] 中间有2行。 - Love Sharma
4
在Python中，您还可以使用itertools.product，它恰好实现了您所编写的功能。 - Thomas Ahle
1
@NickJohnson或其他愿意的人：您能否请添加时间和空间复杂度。 - AnukuL
1
这个的时间和空间复杂度会是多少？谢谢 :) - John Constantine
17

这个问题类似于一个被称为电话号码的字母组合的问题， 这是我的解决方案。
它适用于任意数量的数字，只要结果不超过内存限制就可以。

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位国际电话号码会对设计产生什么影响。

编辑：国际号码也将被处理。

4

使用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);
        }
    }
}
注意：此示例适用于任意长度的电话号码。在某个长度处，它将耗尽内存，因为它必须将每个组合存储在列表中。更改List.add方法调用为println或其他内容，以避免此问题。 - William Brendel
请问您能否解释一下程序的复杂度？ - user1429322
3

在C++（递归）中：

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

这个函数可以在'k'和'i'都为零的情况下调用。

任何需要更多说明来理解逻辑的人，可以将递归技术与以下输出结合使用：

ADG
ADH
ADI

AEG
AEH
AEI

AFG
AFH
AFI


BDG
BDH
BDI

BEG
BEH
BEI

BFG
BFH
...
3
在数字键盘上，文本和数字放置在同一个键上。例如，2有“ABC”，如果我们想要写以“A”开头的任何东西，我们需要按一次2键。如果我们想要输入“B”，则按2键两次，输入“C”则需按三次。下面是这种键盘的图片。 keypad 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，每当它从I重置为G时，左边的数字就会改变。 同样地，每当倒数第二个字母重置其值时，第三个字母就会发生变化，依此类推。第一个字符只在生成所有单词后重置一次。这也可以从另一个角度来看。也就是说，每当位置i处的字符发生变化时，位置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

3
显而易见的解决方案是编写一个将数字映射到键列表的函数，然后编写一个生成可能组合的函数：
第一个函数是显而易见的，第二个函数更为棘手，因为您需要处理约3^数字数量的组合，这可能是非常大的数字。
一种方法是将每个数字匹配的每个可能性看作数字（在基数4上），并实现类似于计数器的东西（跳过某些实例，因为通常有少于4个可映射到数字的字母）。
更明显的解决方案是嵌套循环或递归，它们都不太优雅，但在我看来是有效的。
还要注意避免可扩展性问题（例如，保留可能性在内存中等），因为我们谈论的是大量组合。
附：该问题的另一个有趣扩展是本地化。
使用递归似乎是面向对象革命时代的常态。我喜欢映射的想法，但这似乎更适用于老的 C 语言程序员。 - Todd Moses
1
我认为递归是一种有效的解决方案，但如果在面试中有人没有提供其他解决方案，我可能会拒绝他们（我保证 - 我不是唯一这样想的）。这是常规做法，但在某些环境下（例如手机）- 这太危险了。 - Ofir
快进到2018年，手机变成了智能手机，并且递归在Android中很普遍。 - Abhijit Sarkar
2
在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)
2
这个问题类似于这个Leetcode问题：Letter Combinations of a Phone Number。以下是我提交给Leetcode的答案（请查看GitHub和视频进行解释）。
所以我们需要的第一件事情是一种保存数字映射的方式，我们可以使用一个map：
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次，即复杂度为O(4^n)。"最初的回答"。
1

Python的解决方案非常经济实惠，并且由于使用生成器，在内存使用方面非常高效。

import itertools

keys = dict(enumerate('::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ'.split(':')))

def words(number):
    digits = map(int, str(number))
    for ls in itertools.product(*map(keys.get, digits)):
        yield ''.join(ls)

for w in words(258):
    print w

显然，itertools.product 已经为您解决了大部分问题。但是自己编写也不难。这里提供了一个 Go 语言的解决方案，它小心地重复使用数组 result 来生成所有解决方案，并使用闭包 f 来捕获生成的单词。结合起来，在 product 内部使用 O(log n) 的内存。
package main

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

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

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

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

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

使用Python解决方案

def keypad_words(number):
    
    num_pad_dict = {
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z'],
    }
    result = num_pad_dict.get(number[0], '')
    for i in range(1,len(number)):
        letters = num_pad_dict.get(number[i], '')
        new_result = []
        for prefix in result:  
            for letter in letters:
                new_result.append(prefix+letter)   
            
        result = new_result
    return result
    return []
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接