我刚刚尝试了我的第一次编程面试，其中一个问题是编写一个程序，给定一个 7 位数的电话号码，可以打印每个数字可以代表的所有可能的字母组合。
问题的第二部分是如果这将是一个 12 位数的国际号码呢？这将如何影响您的设计。
我没有我在采访中写的代码，但我觉得他对此并不满意。
做这个的最好方式是什么？
问问题
112410 次
32 回答
44
在 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然后它用现有前缀和可能字母的每个组合替换列表。
于 2010-02-26T22:47:58.407 回答
16
它类似于一个叫做电话号码字母组合的问题，这是我的解决方案。
它适用于任意位数，只要结果不超过内存限制。
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 位国际号码如何影响设计。
编辑：国际号码也将被处理
于 2012-10-01T18:17:07.510 回答
4
在 Java 中使用递归：
import java.util.LinkedList;
import java.util.List;
public class Main {
// Number-to-letter mappings in order from zero to nine
public static String mappings[][] = {
{"0"}, {"1"}, {"A", "B", "C"}, {"D", "E", "F"}, {"G", "H", "I"},
{"J", "K", "L"}, {"M", "N", "O"}, {"P", "Q", "R", "S"},
{"T", "U", "V"}, {"W", "X", "Y", "Z"}
};
public static void generateCombosHelper(List<String> combos,
String prefix, String remaining) {
// The current digit we are working with
int digit = Integer.parseInt(remaining.substring(0, 1));
if (remaining.length() == 1) {
// We have reached the last digit in the phone number, so add
// all possible prefix-digit combinations to the list
for (int i = 0; i < mappings[digit].length; i++) {
combos.add(prefix + mappings[digit][i]);
}
} else {
// Recursively call this method with each possible new
// prefix and the remaining part of the phone number.
for (int i = 0; i < mappings[digit].length; i++) {
generateCombosHelper(combos, prefix + mappings[digit][i],
remaining.substring(1));
}
}
}
public static List<String> generateCombos(String phoneNumber) {
// This will hold the final list of combinations
List<String> combos = new LinkedList<String>();
// Call the helper method with an empty prefix and the entire
// phone number as the remaining part.
generateCombosHelper(combos, "", phoneNumber);
return combos;
}
public static void main(String[] args) {
String phone = "3456789";
List<String> combos = generateCombos(phone);
for (String s : combos) {
System.out.println(s);
}
}
}
于 2010-02-26T20:46:45.670 回答
3
显而易见的解决方案是将数字映射到键列表的函数，然后是生成可能组合的函数：
第一个很明显，第二个问题更大，因为您有大约 3^number 个数字组合，这可能是一个非常大的数字。
一种方法是将数字匹配的每种可能性视为数字中的数字（以 4 为基数）并实现接近计数器的东西（跳过某些实例，因为通常少于 4 个字母可映射到一个数字）。
更明显的解决方案是嵌套循环或递归，它们都不太优雅，但在我看来是有效的。
必须注意的另一件事是避免可伸缩性问题（例如，将可能性保存在内存中等），因为我们正在谈论很多组合。
PS 这个问题的另一个有趣的扩展是本地化。
于 2010-02-26T20:13:04.363 回答
3
在 C++（递归）中：
string pattern[] = {"0",".,!","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};
ofstream keyout("keypad.txt");
void print_keypad(char* str, int k, vector<char> patt, int i){
if(str[k] != '\0')
{
int x = str[k] - '0';
for(int l = 0; l < pattern[x].length(); l++)
{
patt[i] = pattern[x][l];
print_keypad(str, k+1, patt, i+1);
}
keyout << endl;
}
else if(i == k)
{
string st(patt.data());
keyout << st << endl;
return;
}
}
可以在“k”和“i”等于 0 的情况下调用此函数。
任何需要更多插图来理解逻辑的人都可以将递归技术与以下输出相结合：
ADG
ADH
ADI
AEG
AEH
AEI
AFG
AFH
AFI
BDG
BDH
BDI
BEG
BEH
BEI
BFG
BFH
...
于 2012-02-26T21:57:40.537 回答
3
在数字键盘中，文本和数字放在同一个键上。例如 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 是输入数字的位数。
参考：
于 2014-06-28T08:29:24.740 回答
2
在 JavaScript 中。CustomCounter 类负责递增索引。然后只输出不同的可能组合。
var CustomCounter = function(min, max) {
this.min = min.slice(0)
this.max = max.slice(0)
this.curr = this.min.slice(0)
this.length = this.min.length
}
CustomCounter.prototype.increment = function() {
for (var i = this.length - 1, ii = 0; i >= ii; i--) {
this.curr[i] += 1
if (this.curr[i] > this.max[i]) {
this.curr[i] = 0
} else {
break
}
}
}
CustomCounter.prototype.is_max = function() {
for (var i = 0, ii = this.length; i < ii; ++i) {
if (this.curr[i] !== this.max[i]) {
return false
}
}
return true
}
var PhoneNumber = function(phone_number) {
this.phone_number = phone_number
this.combinations = []
}
PhoneNumber.number_to_combinations = {
1: ['1']
, 2: ['2', 'a', 'b', 'c']
, 3: ['3', 'd', 'e', 'f']
, 4: ['4', 'g', 'h', 'i']
, 5: ['5', 'j', 'k', 'l']
, 6: ['6', 'm', 'n', 'o']
, 7: ['7', 'p', 'q', 'r', 's']
, 8: ['8', 't', 'u', 'v']
, 9: ['9', 'w', 'x', 'y', 'z']
, 0: ['0', '+']
}
PhoneNumber.prototype.get_combination_by_digit = function(digit) {
return PhoneNumber.number_to_combinations[digit]
}
PhoneNumber.prototype.add_combination_by_indexes = function(indexes) {
var combination = ''
for (var i = 0, ii = indexes.length; i < ii; ++i) {
var phone_number_digit = this.phone_number[i]
combination += this.get_combination_by_digit(phone_number_digit)[indexes[i]]
}
this.combinations.push(combination)
}
PhoneNumber.prototype.update_combinations = function() {
var min_indexes = []
, max_indexes = []
for (var i = 0, ii = this.phone_number.length; i < ii; ++i) {
var digit = this.phone_number[i]
min_indexes.push(0)
max_indexes.push(this.get_combination_by_digit(digit).length - 1)
}
var c = new CustomCounter(min_indexes, max_indexes)
while(true) {
this.add_combination_by_indexes(c.curr)
c.increment()
if (c.is_max()) {
this.add_combination_by_indexes(c.curr)
break
}
}
}
var phone_number = new PhoneNumber('120')
phone_number.update_combinations()
console.log(phone_number.combinations)
于 2014-10-18T20:47:19.300 回答
2
这个问题类似于这个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
}
现在方法体可以填充为（结果将保存在列表中，字符串生成器中的临时等）
private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) {
if(start >= digits.length()) { // condition
result.add(temp.toString());
return;
}
String letters = getDigitMappings(digits.substring(start, start + 1), digitMap); // mappings of a digit to loop around
for (int i = 0; i < letters.length(); i++) {
temp.append(letters.charAt(i));
compute(result, temp, digits, start+1, digitMap); //explore for remaining digits
temp.deleteCharAt(temp.length() - 1); // remove last in temp
}
}
最后，该方法可以调用为：
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if(digits == null || digits.length() == 0) return result;
compute(result, new StringBuilder(), digits, 0, getDigitMap());
return result;
}
现在，一个数字的最大映射字符可以是 4（例如 9 具有 wxyz），并且回溯涉及详尽搜索以探索所有可能的排列（状态空间树），因此对于一个大小的数字，n我们将拥有4x4x4....n times即复杂性O(4^n)。
于 2019-02-03T03:45:54.683 回答
1
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
于 2011-12-22T14:38:05.310 回答
1
Python 解决方案非常经济，因为它使用生成器在内存使用方面非常有效。
import itertools
keys = dict(enumerate('::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ'.split(':')))
def words(number):
digits = map(int, str(number))
for ls in itertools.product(*map(keys.get, digits)):
yield ''.join(ls)
for w in words(258):
print w
显然itertools.product正在为您解决大部分问题。但是自己写并不难。这是go中的一个解决方案，它小心地重复使用数组result来生成所有解决方案，并使用闭包f来捕获生成的单词。结合起来，这些给 O(log n) 内存使用 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)) })
}
于 2015-03-25T01:12:04.267 回答
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;
}
}
}
}
于 2010-02-26T20:22:30.347 回答
1
使用列表 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 种可能性，这并不多。如果您需要所有组合，我看不到更好的方法。你可以避免递归等等，但无论如何你都不会得到比这快得多的东西。
于 2010-02-26T20:25:42.547 回答
1
#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;
}
于 2012-06-02T11:58:58.833 回答
1
这是此答案的 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);
}
}
于 2015-12-15T02:22:14.103 回答
0
您可以在此处找到源代码 (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)
是人类可能观察到的东西——让算法找到这些东西是相当困难的。
于 2012-03-25T23:49:59.390 回答
0
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');
于 2010-03-01T12:19:29.140 回答
0
我是一个新手，所以请在我错的地方纠正我。
首先是研究空间和时间复杂度。这真的很糟糕，因为它是阶乘，所以对于 factorial(7) = 5040 任何递归算法都可以。但是对于 factorial(12) ~= 4 * 10^8 这可能会导致递归解决方案中的堆栈溢出。
所以我不会尝试递归算法。使用“Next Permutation”循环解决方案非常简单。
所以我会创建和排列 {0, 1, 2, 3, 4, 5} 并生成所有排列，并在打印时用相应的字符替换它们，例如。0=A, 5=F
Next Perm 算法的工作原理如下。例如，给定 1,3,5,4 下一个排列是 1,4,3,5
寻找下一个烫发的步骤。
从右到左，找到第一个递减的数字。例如 3
从左到右，找到大于 3 的最小数字，例如。4
交换这些数字作为反向子集。1,4,5,3 反向子集 1,4,3,5
使用下一个排列（或旋转），您可以生成特定的排列子集，例如您想要显示从特定电话号码开始的 1000 个排列。这可以使您免于将所有数字都保存在内存中。如果我将数字存储为 4 字节整数，则 10^9 字节 = 1 GB ！。
于 2011-12-22T22:07:51.573 回答
0
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;
}
}
于 2014-10-09T21:12:23.897 回答
0
这是 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;
}
于 2013-09-04T19:23:17.293 回答
0
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;
}
于 2011-02-22T19:10:05.207 回答
0
这是一个用于疼痛 C 的。这个可能不是有效的（实际上我认为根本不是）。但它有一些有趣的方面。
- 它需要一个数字并将其转换为字符串
- 它每次只增加一次种子数以创建下一个顺序字符串
这样做的好处是对字符串的大小没有真正的限制（没有字符限制）这允许您在需要时仅通过等待来生成越来越长的字符串。
#include <stdlib.h>
#include <stdio.h>
#define CHARACTER_RANGE 95 // The range of valid password characters
#define CHARACTER_OFFSET 32 // The offset of the first valid character
void main(int argc, char *argv[], char *env[])
{
int i;
long int string;
long int worker;
char *guess; // Current Generation
guess = (char*)malloc(1); // Allocate it so free doesn't fail
int cur;
for ( string = 0; ; string++ )
{
worker = string;
free(guess);
guess = (char*)malloc((string/CHARACTER_RANGE+1)*sizeof(char)); // Alocate for the number of characters we will need
for ( i = 0; worker > 0 && i < string/CHARACTER_RANGE + 1; i++ ) // Work out the string
{
cur = worker % CHARACTER_RANGE; // Take off the last digit
worker = (worker - cur) / CHARACTER_RANGE; // Advance the digits
cur += CHARACTER_OFFSET;
guess[i] = cur;
}
guess[i+1] = '\0'; // NULL terminate our string
printf("%s\t%d\n", guess, string);
}
}
于 2010-11-24T23:34:13.173 回答
0
C# 中的这个版本相当有效，它适用于非西方数字（例如“12234557”）。
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' }
};
于 2010-02-26T21:22:55.053 回答
0
/**
* 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);
}
}
}
于 2011-06-10T21:38:15.023 回答
0
这是相同的工作代码..它对每个步骤的递归检查在系列中出现相同数字时每个组合的可能性....从复杂性的角度来看，我不确定是否有更好的解决方案......
如有任何问题请告诉我......
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;
}
}
于 2012-01-22T23:54:43.077 回答
0
我已经实现了一个有助于减少递归次数的缓存。此缓存将避免扫描它已经为以前的组合完成的字母。例如，它需要 120k 循环，在缓存实现之后它减少到 40k。
private List<String> generateWords(String phoneNumber) {
List<String> words = new LinkedList<String>();
List<String> wordsCache = new LinkedList<String>();
this.generatePossibleWords("", phoneNumber, words, wordsCache);
return words;
}
private void generatePossibleWords(String prefix, String remainder,
List<String> words, List<String> wordsCache) {
int index = Integer.parseInt(remainder.substring(0, 1));
for (int i = 0; i < phoneKeyMapper.get(index).size(); i++) {
String mappedChar = phoneKeyMapper.get(index).get(i);
if (prefix.equals("") && !wordsCache.isEmpty()) {
for (String word : wordsCache) {
words.add(mappedChar + word);
}
} else {
if (remainder.length() == 1) {
String stringToBeAdded = prefix + mappedChar;
words.add(stringToBeAdded);
wordsCache.add(stringToBeAdded.substring(1));
LOGGER.finest("adding stringToBeAdded = " + stringToBeAdded.substring(1));
} else {
generatePossibleWords(prefix + mappedChar,
remainder.substring(1), words, wordsCache);
}
}
}
}
private void createPhoneNumberMapper() {
if (phoneKeyMapper == null) {
phoneKeyMapper = new ArrayList<>();
phoneKeyMapper.add(0, new ArrayList<String>());
phoneKeyMapper.add(1, new ArrayList<String>());
phoneKeyMapper.add(2, new ArrayList<String>());
phoneKeyMapper.get(2).add("A");
phoneKeyMapper.get(2).add("B");
phoneKeyMapper.get(2).add("C");
phoneKeyMapper.add(3, new ArrayList<String>());
phoneKeyMapper.get(3).add("D");
phoneKeyMapper.get(3).add("E");
phoneKeyMapper.get(3).add("F");
phoneKeyMapper.add(4, new ArrayList<String>());
phoneKeyMapper.get(4).add("G");
phoneKeyMapper.get(4).add("H");
phoneKeyMapper.get(4).add("I");
phoneKeyMapper.add(5, new ArrayList<String>());
phoneKeyMapper.get(5).add("J");
phoneKeyMapper.get(5).add("K");
phoneKeyMapper.get(5).add("L");
phoneKeyMapper.add(6, new ArrayList<String>());
phoneKeyMapper.get(6).add("M");
phoneKeyMapper.get(6).add("N");
phoneKeyMapper.get(6).add("O");
phoneKeyMapper.add(7, new ArrayList<String>());
phoneKeyMapper.get(7).add("P");
phoneKeyMapper.get(7).add("Q");
phoneKeyMapper.get(7).add("R");
phoneKeyMapper.get(7).add("S");
phoneKeyMapper.add(8, new ArrayList<String>());
phoneKeyMapper.get(8).add("T");
phoneKeyMapper.get(8).add("U");
phoneKeyMapper.get(8).add("V");
phoneKeyMapper.add(9, new ArrayList<String>());
phoneKeyMapper.get(9).add("W");
phoneKeyMapper.get(9).add("X");
phoneKeyMapper.get(9).add("Y");
phoneKeyMapper.get(9).add("Z");
}
}
于 2015-03-24T22:48:13.283 回答
0
我重写了这个（上面提到的）的最新答案，从 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();
}
于 2014-06-30T06:33:50.367 回答
0
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;
}
于 2015-09-15T16:35:27.500 回答
0
使用嵌套循环的 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 解决方案。
于 2016-09-04T19:37:53.330 回答
0
斯卡拉解决方案：
def mnemonics(phoneNum: String, dict: IndexedSeq[String]): Iterable[String] = {
def mnemonics(d: Int, prefix: String): Seq[String] = {
if (d >= phoneNum.length) {
Seq(prefix)
} else {
for {
ch <- dict(phoneNum.charAt(d).asDigit)
num <- mnemonics(d + 1, s"$prefix$ch")
} yield num
}
}
mnemonics(0, "")
}
假设每个数字最多映射 4 个字符，递归调用的数量T满足不等式T(n) <= 4T(n-1)，即4^n。
于 2018-07-22T02:51:13.353 回答
0
在一次工作面试中，我收到了这个关于创建一个数组并打印出电话号码所有可能的字母组合的问题。在面试期间，我收到了面试官关于递归以及如何使用循环无法完成的耳语。从另一个程序员那里得到输入对我来说非常不自然，我相信他的建议而不是我自己的学费，然后开始写一个草率的递归混乱。它并不顺利。在收到输入之前，因为我以前从未收到过这个问题，我的大脑正在计算潜在的可复制数学公式。我低声说：“不能只乘以三，其中一些是四”，因为我的大脑开始与一个短时钟赛跑，一边思考一个答案，一边开始写另一个答案。直到周末，我才接到我的电话，让我知道这个悲伤的消息。那天晚上晚些时候，我决定看看这是否真的是一个递归问题。结果对我来说不是。
我下面的解决方案是用 PHP 编码的，是非递归的，适用于任何长度的输入，我什至包含了一些注释来帮助描述我的变量的含义。这是我对这个问题的官方和不变的最终答案。我希望这对将来的其他人有所帮助，请随时将其翻译成其他语言。
Me 方法涉及计算组合的总数并创建一个足够大的缓冲区以容纳每个字节。我的缓冲区的长度与您期望从有效的递归算法中接收到的长度相同。我创建了一个数组，其中包含代表每个数字的字母组。我的方法主要是因为你的组合总数总是可以被当前组中的字母数整除。如果您可以在脑海中想象该算法的输出的垂直列表，或者垂直查看列表而不是水平书写的组合列表，那么我的算法将开始有意义。该算法允许我们从左到右从上到下垂直循环每个字节，而不是从左到右水平循环，并单独填充每个字节而不需要递归。
非递归、迭代 PHP
<?php
// Display all possible combinations of letters for each number.
$input = '23456789';
// ====================
if(!isset($input[0]))
die('Nothing to see here!');
$phone_letters = array(
2 => array('a', 'b', 'c'),
3 => array('d', 'e', 'f'),
4 => array('g', 'h', 'i'),
5 => array('j', 'k', 'l'),
6 => array('m', 'n', 'o'),
7 => array('p', 'q', 'r', 's'),
8 => array('t', 'u', 'v'),
9 => array('w', 'x', 'y', 'z')
);
$groups = array();
$combos_total = 1;
$l = strlen($input);
for($i = 0; $i < $l; ++$i) {
$groups[] = $phone_letters[$input[$i]];
$combos_total *= count($phone_letters[$input[$i]]);
}
$count = $combos_total / count($groups[0]);
$combos = array_fill(0, $combos_total, str_repeat(chr(0), strlen($input)));
for(
$group = 0, // Index for the current group of letters.
$groups_count = count($groups), // Total number of letter groups.
$letters = count($groups[0]), // Total number of letters in the current group.
$width = $combos_total, // Number of bytes to repeat the current letter.
$repeat = 1; // Total number of times the group will repeat.
;
) {
for($byte = 0, $width /= $letters, $r = 0; $r < $repeat; ++$r)
for($l = 0; $l < $letters; ++$l)
for($w = 0; $w < $width; ++$w)
$combos[$byte++][$group] = $groups[$group][$l];
if(++$group < $groups_count) {
$repeat *= $letters;
$letters = count($groups[$group]);
}
else
break;
}
// ====================
if(is_array($combos)) {
print_r($combos);
echo 'Total combos:', count($combos), "\n";
}
else
echo 'No combos.', "\n";
echo 'Expected combos: ', $combos_total, "\n";
非递归、非迭代、无缓冲区、线程友好、仅数学 + 使用多基大端序的非递归、迭代 PHP 对象
前几天我在新房子里工作时，我意识到我可以使用我的第一个函数中的数学以及我的基础知识来将我输入的所有可能的字母组合视为一个多维数。
我的对象提供了将首选组合存储到数据库中所需的功能，在需要时转换字母和数字，使用首选组合或字节从组合空间中的任何位置挑选组合，这一切都非常适合多线程.
话虽如此，使用我的对象，我可以提供第二个答案，它使用基数、无缓冲区、无迭代，最重要的是无递归。
<?php
class phone {
public static $letters = array(
2 => array('a', 'b', 'c'),
3 => array('d', 'e', 'f'),
4 => array('g', 'h', 'i'),
5 => array('j', 'k', 'l'),
6 => array('m', 'n', 'o'),
7 => array('p', 'q', 'r', 's'),
8 => array('t', 'u', 'v'),
9 => array('w', 'x', 'y', 'z')
);
// Convert a letter into its respective number.
public static function letter_number($letter) {
if(!isset($letter[0]) || isset($letter[1]))
return false;
for($i = 2; $i < 10; ++$i)
if(in_array($letter, phone::$letters[$i], true))
return $i;
return false;
}
// Convert letters into their respective numbers.
public static function letters_numbers($letters) {
if(!isset($letters[0]))
return false;
$length = strlen($letters);
$numbers = str_repeat(chr(0), $length);
for($i = 0; $i < $length; ++$i) {
for($j = 2; $j < 10; ++$j) {
if(in_array($letters[$i], phone::$letters[$j], true)) {
$numbers[$i] = $j;
break;
}
}
}
return $numbers;
}
// Calculate the maximum number of combinations that could occur within a particular input size.
public static function combination_size($groups) {
return $groups <= 0 ? false : pow(4, $groups);
}
// Calculate the minimum bytes reqired to store a group using the current input.
public static function combination_bytes($groups) {
if($groups <= 0)
return false;
$size = $groups * 4;
$bytes = 0;
while($groups !== 0) {
$groups >> 8;
++$bytes;
}
return $bytes;
}
public $input = '';
public $input_len = 0;
public $combinations_total = 0;
public $combinations_length = 0;
private $iterations = array();
private $branches = array();
function __construct($number) {
if(!isset($number[0]))
return false;
$this->input = $number;
$input_len = strlen($number);
$combinations_total = 1;
for($i = 0; $i < $input_len; ++$i) {
$combinations_total *= count(phone::$letters[$number[$i]]);
}
$this->input_len = $input_len;
$this->combinations_total = $combinations_total;
$this->combinations_length = $combinations_total * $input_len;
for($i = 0; $i < $input_len; ++$i) {
$this->branches[] = $this->combination_branches($i);
$this->iterations[] = $this->combination_iteration($i);
}
}
// Calculate a particular combination in the combination space and return the details of that combination.
public function combination($combination) {
$position = $combination * $this->input_len;
if($position < 0 || $position >= $this->combinations_length)
return false;
$group = $position % $this->input_len;
$first = $position - $group;
$last = $first + $this->input_len - 1;
$combination = floor(($last + 1) / $this->input_len) - 1;
$bytes = str_repeat(chr(0), $this->input_len);
for($i = 0; $i < $this->input_len; ++$i)
$bytes[$i] = phone::$letters[$this->input[$i]][($combination / $this->branches[$i]) % count(phone::$letters[$this->input[$i]])];
return array(
'combination' => $combination,
'branches' => $this->branches[$group],
'iterations' => $this->iterations[$group],
'first' => $first,
'last' => $last,
'bytes' => $bytes
);
}
// Calculate a particular byte in the combination space and return the details of that byte.
public function combination_position($position) {
if($position < 0 || $position >= $this->combinations_length)
return false;
$group = $position % $this->input_len;
$group_count = count(phone::$letters[$this->input[$group]]);
$first = $position - $group;
$last = $first + $this->input_len - 1;
$combination = floor(($last + 1) / $this->input_len) - 1;
$index = ($combination / $this->branches[$group]) % $group_count;
$bytes = str_repeat(chr(0), $this->input_len);
for($i = 0; $i < $this->input_len; ++$i)
$bytes[$i] = phone::$letters[$this->input[$i]][($combination / $this->branches[$i]) % count(phone::$letters[$this->input[$i]])];
return array(
'position' => $position,
'combination' => $combination - 1,
'group' => $group,
'group_count' => $group_count,
'group_index' => $index,
'number' => $this->input[$group],
'branches' => $this->branches[$group],
'iterations' => $this->iterations[$group],
'first' => $first,
'last' => $last,
'byte' => phone::$letters[$this->input[$group]][$index],
'bytes' => $bytes
);
}
// Convert letters into a combination number using Multi-Base Big Endian.
public function combination_letters($letters) {
if(!isset($letters[$this->input_len - 1]) || isset($letters[$this->input_len]))
return false;
$combination = 0;
for($byte = 0; $byte < $this->input_len; ++$byte) {
$base = count(phone::$letters[$this->input[$byte]]);
$found = false;
for($value = 0; $value < $base; ++$value) {
if($letters[$byte] === phone::$letters[$this->input[$byte]][$value]) {
$combination += $value * $this->branches[$byte];
$found = true;
break;
}
}
if($found === false)
return false;
}
return $combination;
}
// Calculate the number of branches after a particular group.
public function combination_branches($group) {
if($group >= 0 && ++$group < $this->input_len) {
$branches = 1;
for($i = $group; $i < $this->input_len; ++$i)
$branches *= count(phone::$letters[$this->input[$i]]);
return $branches === 1 ? 1 : $branches;
}
elseif($group === $this->input_len)
return 1;
else
return false;
}
// Calculate the number of iterations before a particular group.
public function combination_iteration($group) {
if($group > 0 && $group < $this->input_len) {
$iterations = 1;
for($i = $group - 1; $i >= 0; --$i)
$iterations *= count(phone::$letters[$this->input[$i]]);
return $iterations;
}
elseif($group === 0)
return 1;
else
return false;
}
// Iterations, Outputs array of all combinations using a buffer.
public function combinations() {
$count = $this->combinations_total / count(phone::$letters[$this->input[0]]);
$combinations = array_fill(0, $this->combinations_total, str_repeat(chr(0), $this->input_len));
for(
$group = 0, // Index for the current group of letters.
$groups_count = $this->input_len, // Total number of letter groups.
$letters = count(phone::$letters[$this->input[0]]), // Total number of letters in the current group.
$width = $this->combinations_total, // Number of bytes to repeat the current letter.
$repeat = 1; // Total number of times the group will repeat.
;
) {
for($byte = 0, $width /= $letters, $r = 0; $r < $repeat; ++$r)
for($l = 0; $l < $letters; ++$l)
for($w = 0; $w < $width; ++$w)
$combinations[$byte++][$group] = phone::$letters[$this->input[$group]][$l];
if(++$group < $groups_count) {
$repeat *= $letters;
$letters = count(phone::$letters[$this->input[$group]]);
}
else
break;
}
return $combinations;
}
}
// ====================
$phone = new phone('23456789');
print_r($phone);
//print_r($phone->combinations());
for($i = 0; $i < $phone->combinations_total; ++$i) {
echo $i, ': ', $phone->combination($i)['bytes'], "\n";
}
于 2019-04-13T15:36:40.540 回答
0
我在 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')
于 2016-08-23T23:30:52.227 回答
0
这种方法使用 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"
于 2017-01-06T22:19:52.497 回答