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

发布于 2024-08-22 23:11:51 字数 173 浏览 7 评论 0 原文

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

问题的第二部分是如果这是一个 12 位国际号码怎么办?这将如何影响您的设计。

我没有在采访中编写的代码,但我的印象是他对此不满意。
最好的方法是什么?

I just tried for my first programming interview and one of the questions was to write a program that given a 7 digit telephone number, could print all possible combinations of letters that each number could represent.

A second part of the question was like what about if this would have been a 12 digit international number? How would that effect your design.

I don't have the code that I wrote in the interview, but I got the impression he wasn't happy with it.
What is the best way to do this?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(30

黎歌 2024-08-29 23:11:51

在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

In Python, iterative:

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 is a list of results so far; initially it is populated with one item, the empty string. Then, for each character in the input string, it looks up the list of letters that match it from the dict defined at the top. It then replaces the list ret with the every combination of existing prefix and possible letter.

梦旅人picnic 2024-08-29 23:11:51

它类似于电话号码的字母组合,
这是我的解决方案。
它适用于任意数量的数字,只要结果不超过内存限制即可。

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 位国际号码如何影响设计。

编辑:国际号码也将得到处理

It is similar to a question called letter combinations of a phone number,
here is my solution.
It works for an arbitrary number of digits, so long as the result doesn't exceed the memory limit.

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', "");
    }} ;
}

I'm not sure how 12-digit international numbers affect the design.

Edit: International numbers will also be handled

请远离我 2024-08-29 23:11:51

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

In Java using recursion:

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);
        }
    }
}
尾戒 2024-08-29 23:11:51

显而易见的解决方案是将数字映射到键列表的函数,然后是生成可能组合的函数:

第一个很明显,第二个更成问题,因为您有大约 3^ 个数字组合,这可以是一个非常大的数字。

一种方法是将数字匹配为数字中的数字(以 4 为基数)的每种可能性,并实现一些接近计数器的东西(跳过某些实例,因为通常可映射到数字的字母少于 4 个) )。

更明显的解决方案是嵌套循环或递归,它们都不太优雅,但在我看来是有效的。

必须注意的另一件事是避免可扩展性问题(例如,将可能性保留在内存中等),因为我们正在讨论很多组合。

PS 这个问题的另一个有趣的延伸是本地化。

The obvious solution is a function to map a digit to a list of keys, and then a function that would generate the possible combinations:

The first is obvious, the second is more problematic because you have around 3^number of digits combinations, which can be a very large number.

One way to do it is to look at each possibility for digit matching as a digit in a number (on base 4) and implement something close to a counter (jumping over some instances, since there are usually less than 4 letters mappable to a digit).

The more obvious solutions would be nested loops or recursion, which are both less elegant, but in my opinion valid.

Another thing for which care must be taken is to avoid scalability issues (e.g. keeping the possibilities in memory, etc.) since we are talking about a lot of combinations.

P.S. Another interesting extension of the question would be localization.

甜扑 2024-08-29 23:11:51

在 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”等于 0 来调用该函数。

任何需要更多插图来理解逻辑的人都可以将递归技术与以下输出结合起来:

ADG
ADH
ADI

AEG
AEH
AEI

AFG
AFH
AFI


BDG
BDH
BDI

BEG
BEH
BEI

BFG
BFH
...

In C++(recursive):

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

This function can be called with 'k' and 'i' equal to zero.

Anyone, who requires more illustration to understand the logic, can combine recursion technique with following output:

ADG
ADH
ADI

AEG
AEH
AEI

AFG
AFH
AFI


BDG
BDH
BDI

BEG
BEH
BEI

BFG
BFH
...
一指流沙 2024-08-29 23:11:51

在数字键盘中,文本和数字位于同一个键上。例如,2 有“ABC”,如果我们想写入以“A”开头的任何内容,我们需要输入键 2 一次。如果我们想输入“B”,请按 2 键两次并三次以输入“C”。下面是此类键盘的图片。

键盘 http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard .png

给定如图所示的键盘和一个数字,列出按这些数字可能出现的所有单词。

例如,如果输入数字是 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 实现,用于打印与数字输入数字对应的所有可能的单词。请注意,输入数字表示为数组以简化代码。

#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-expose-secrets-landing-your-next-job-3rd/p/itmdxghumef3sdjn?pid=9788126539116&affid=sandeepgfg

In numeric keyboards, texts and numbers are placed on the same key. For example 2 has “ABC” if we wanted to write anything starting with ‘A’ we need to type key 2 once. If we wanted to type ‘B’, press key 2 twice and thrice for typing ‘C’. below is picture of such keypad.

keypad http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard.png

Given a keypad as shown in diagram, and a n digit number, list all words which are possible by pressing these numbers.

For example if input number is 234, possible words which can be formed are (Alphabetical order):
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

Let’s do some calculations first. How many words are possible with seven digits with each digit representing n letters? For first digit we have at most four choices, and for each choice for first letter, we have at most four choices for second digit and so on. So it’s simple maths it will be O(4^n). Since keys 0 and 1 don’t have any corresponding alphabet and many characters have 3 characters, 4^n would be the upper bound of number of words and not the minimum words.

Now let’s do some examples.

For number above 234. Do you see any pattern? Yes, we notice that the last character always either G,H or I and whenever it resets its value from I to G, the digit at the left of it gets changed.
Similarly whenever the second last alphabet resets its value, the third last alphabet gets changes and so on. First character resets only once when we have generated all words. This can be looked from other end also. That is to say whenever character at position i changes, character at position i+1 goes through all possible characters and it creates ripple effect till we reach at end.
Since 0 and 1 don’t have any characters associated with them. we should break as there will no iteration for these digits.

Let’s take the second approach as it will be easy to implement it using recursion. We go till the end and come back one by one. Perfect condition for recursion. let’s search for base case.
When we reach at the last character, we print the word with all possible characters for last digit and return. Simple base case.When we reach at the last character, we print the word with all possible characters for last digit and return. Simple base case.

Following is C implementation of recursive approach to print all possible word corresponding to a n digit input number. Note that input number is represented as an array to simplify the code.

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

Output:

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

Time Complexity:

Time complexity of above code is O(4^n) where n is number of digits in input number.

References:

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

时间海 2024-08-29 23:11:51

在 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)

In JavaScript. A CustomCounter class takes care of incrementing indexes. Then just output the different possible combinations.

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)
静若繁花 2024-08-29 23:11:51

这个问题类似于这个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
}

现在可以填充方法主体as(结果将保存在列表中,临时保存在字符串生成器等中)

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)。

This problem is similar to this leetcode problem. Here is the answer I submitted for this problem to leetcode (check github and video for explanation).

So the very first thing we need is some way to hold the mappings of a digit and we can use a map for this:

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

The above method is preparing the map and next method I would use is to provide the mapping for provided digit:

private String getDigitMappings(String strDigit, Map<Integer,String> digitMap) {
        int digit = Integer.valueOf(strDigit);
        return digitMap.containsKey(digit) ? digitMap.get(digit) : "";
}

This problem can be solved using backtracking and a backtracking solution generally has a structure where the method signature will contain: result container, temp results, original source with index etc. So the method structure would be of the form:

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
}

And now the method body can be filled as (result will be kept in a list, temp in string builder etc.)

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

And finally the method can be invoked as:

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

Now the max mapped chars for a digit can be 4 (e.g. 9 has wxyz) and backtracking involves exhaustive search to explore all possible arrangements (state space tree) so for a digit of size n we are going to have 4x4x4....n times i.e. complexity would be O(4^n).

落花随流水 2024-08-29 23:11:51
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;
            }
        }
    }
}
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;
            }
        }
    }
}
触ぅ动初心 2024-08-29 23:11:51

使用列表 L,其中 L[i] = 数字 i 可以表示的符号。

L[1] = @,.,! (例如)
L[2] = a,b,c

等等。

那么你可以这样做(伪 C):

void f(int k, int st[])
{
  if ( k > numberOfDigits )
  {
    print contents of st[];
    return;
  }

  for each character c in L[Digit At Position k]
  {
    st[k] = c;
    f(k + 1, st);
  }
}

假设每个列表包含 3 个字符,则 7 个数字有 3^7 种可能性,12 个数字有 3^12 种可能性,这是没有那么多。如果您需要所有组合,我看不出更好的方法。你可以避免递归之类的东西,但无论如何你都不会得到比这更快的东西。

Use a list L where L[i] = the symbols that digit i can represent.

L[1] = @,.,! (for example)
L[2] = a,b,c

Etc.

Then you can do something like this (pseudo-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);
  }
}

Assuming each list contains 3 characters, we have 3^7 possibilities for 7 digits and 3^12 for 12, which isn't that many. If you need all combinations, I don't see a much better way. You can avoid recursion and whatnot, but you're not going to get something a lot faster than this no matter what.

压抑⊿情绪 2024-08-29 23:11:51
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
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
夏末染殇 2024-08-29 23:11:51
#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;
}
#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;
}
自我难过 2024-08-29 23:11:51

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

A Python solution is quite economical, and because it uses generators is efficient in terms of memory use.

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

Obviously itertools.product is solving most of the problem for you. But writing it oneself is not difficult. Here's a solution in go, which is careful to re-use the array result to generate all solutions in, and a closure f to capture the generated words. Combined, these give O(log n) memory use inside 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)) })
}
生生漫 2024-08-29 23:11:51

这是这个答案的C#端口。

代码

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

This is the C# port of this answer.

Code

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

Unit Tests

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);
    }
}
孤独患者 2024-08-29 23:11:51

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 []

Python solution with

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 []
昵称有卵用 2024-08-29 23:11:51

C# 中的这个版本相当高效,并且适用于非西方数字(例如“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' }
};

This version in C# is reasonably efficient, and it works for non-western digits (like "۱۲۳۴۵۶۷" for example).

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' }
};
花开浅夏 2024-08-29 23:11:51

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

Oracle SQL: Usable with any phone number length and can easily support localization.

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');
心欲静而疯不止 2024-08-29 23:11:51

这是一种针对疼痛 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);
    }
}

Here is one for pain C. This one is likley not efficet (in fact I don't think it is at all). But there are some intresting aspects to it.

  1. It take a number and converts it into a string
  2. It just raises the seed number once each time to create the next sequential string

Whats nice about this is that there is no real limit to the size of the string (no character limit) This allows you to generate longer and longer strings if need be just by waiting.

#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);
    }
}
以酷 2024-08-29 23:11:51
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;
    }
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;
    }
月下凄凉 2024-08-29 23:11:51
/**
 * 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);
        }
    }
}
/**
 * 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);
        }
    }
}
电影里的梦 2024-08-29 23:11:51

我是个新手,所以有错误的地方请指正。

第一件事是研究太空和时间复杂度。这真的很糟糕,因为它是阶乘
因此对于阶乘(7) = 5040,任何递归算法都可以。但对于阶乘(12) ~= 4 * 10^8 ,这可能会导致递归解决方案中的堆栈溢出。

所以我不会尝试递归算法。使用“Next Permutation”循环解决方案非常简单。

因此,我将创建数组 {0, 1, 2, 3, 4, 5} 并生成所有排列,并在打印时将它们替换为相应的字符,例如。 0=A, 5=F

接下来 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 GB!。

I am rather a newbie so please correct me wherever I am wrong.

First thing is looking into space & time complexity. Which is really bad since it's factorial
so for factorial(7) = 5040 any recursive algorithm would do. But for factorial(12) ~= 4 * 10^8 which can cause stack overflow in recursive solution.

So I would not attempt a recursive algorithm. Looping solution is very straight forward using "Next Permutation".

So I would create and array {0, 1, 2, 3, 4, 5} and generate all permutation and while printing replace them with respective characters eg. 0=A, 5=F

Next Perm algorithm works as follows. eg Given 1,3,5,4 next permutation is 1,4,3,5

Steps for finding next perm.

  1. From right to left, find first decreasing number. eg 3

  2. From left to right, find lowest number bigger than 3 eg. 4

  3. Swap these numbers as reverse the subset. 1,4,5,3 reverse subset 1,4,3,5

Using Next permutation ( or rotation) you generate specific subset of permutations, say you want to show 1000 permutations starting from a particular phone number. This can save you from having all numbers in memory. If I store numbers as 4 byte integers, 10^9 bytes = 1 GB !.

两人的回忆 2024-08-29 23:11:51

这是相同的工作代码..
它是每个步骤的递归,检查一系列中出现相同数字时每个组合的可能性......我不确定从复杂性的角度来看是否有更好的解决方案......

请告诉我有任何问题....

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;

    }

}

Here is the working code for the same..
its a recursion on each step checking possibility of each combinations on occurrence of same digit in a series....I am not sure if there is any better solution then this from complexity point of view.....

Please let me know for any issues....

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;

    }

}
桃气十足 2024-08-29 23:11:51

您可以在此处找到源代码 (Scala)此处是一个工作小程序。

由于 0 和 1 与字符不匹配,因此它们在数字中构建自然断点。但它们并不出现在每个数字中(开头的 0 除外)。较长的数字(例如从 9 位数字开始的 +49567892345)可能会导致 OutOfMemoryErrors。因此,最好将数字分成

  • 01723 5864
  • 0172 35864

等组,看看是否可以从较短的部分中理解。我写了一个这样的程序,并测试了朋友提供的一些数字,但很少发现短单词的组合,可以在字典中查找匹配,更不用说单个长单词了。

因此,我的决定是仅支持搜索,不支持完全自动化,通过显示可能的组合,鼓励手动拆分数字,也许可以多次。

所以我找到了+-RAD JUNG(+-自行车男孩)。

如果你接受拼写错误、缩写、外来词、数字作为单词、数字作为单词和名称,那么你找到解决方案的机会比不乱搞要好得多。

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

是人类可能观察到的东西——让算法找到这样的东西是相当困难的。

You find source (Scala) here and an working applet here.

Since 0 and 1 aren't matched to characters, they build natural breakpoints in numbers. But they don't occur in every number (except 0 at the beginning). Longer numbers like +49567892345 from 9 digits starting, can lead to OutOfMemoryErrors. So it would be better to split a number into groups like

  • 01723 5864
  • 0172 35864

to see, if you can make sense from the shorter parts. I wrote such a program, and tested some numbers from my friends, but found rarely combinations of shorter words, which could be checked in a dictionary for matching, not to mention single, long words.

So my decision was to only support searching, no full automation, by displaying possible combinations, encouraging splitting the number by hand, maybe multiple time.

So I found +-RAD JUNG (+-bycicle boy).

If you accept misspellings, abbreviations, foreign words, numbers as words, numbers in words, and names, your chance to find a solution is much better, than without fiddling around.

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

are things a human might observe - to make an algorithm find such things is rather hard.

乞讨 2024-08-29 23:11:51

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

This is a recursive algorithm in 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;
}
你列表最软的妹 2024-08-29 23:11:51

我重写了对此的最新答案(上面提到的),从 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();
}

I rewrote the latest answer to this (referred above) , from C to Java. I also included the support for 0 and 1 (as 0 and 1) because numbers such as 555-5055 weren't working at all with the above code.

Here it is. Some comments are preserved.

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();
}
诗笺 2024-08-29 23:11:51
    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;
        }
    }
    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;
        }
    }
倾城月光淡如水﹏ 2024-08-29 23:11:51

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

One option in 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;
}

烂柯人 2024-08-29 23:11:51

我在 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')

I tried it in ruby, and came up with a different way of doing, it's probably not efficient, like time and space O(?) at this point, but I like it because it uses Ruby's builtin Array.product method. What do you think?

EDIT: I see a very similar solution in Python above, but I hadn't seen it when I added my answer

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')
灯角 2024-08-29 23:11:51

使用嵌套循环的 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 解决方案,使用更多循环和采样

An R solution using nested loops:

# 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

I posted another, more bizarre R solution using more loops and sampling on my blog.

过潦 2024-08-29 23:11:51

该方法使用 R,首先将字典转换为其相应的数字表示形式,然后将其用作查找。

在我的机器上,转换只需要 1 秒(从大约 100,000 个单词的本机 Unix 字典转换),典型的最多 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"

This approach uses R and is based on first converting the dictionary to its corresponding digit representation, then using this as a look-up.

The conversion only takes 1 second on my machine (converting from the native Unix dictionary of about 100,000 words), and typical look-ups of up to 100 different digit inputs take a total of .1 seconds:

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"
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文