我有 2 天的面试，我很难找到这个问题的解决方案：我想要做的是 .. 对于任何电话号码 .. 程序应该打印出它代表的所有可能的字符串。例如）数字中的 2 可以替换为“a”或“b”或“c”，3 可以替换为“d”“e”“f”等。这样可以从 a 中形成多少种可能的排列给定的电话号码。我不希望任何人为它编写代码......一个好的算法或伪代码会很棒。
谢谢
问问题
11137 次
10 回答
8
这是流行的对应表：
d = { '2': "ABC",
'3': "DEF",
'4': "GHI",
'5': "JKL",
'6': "MNO",
'7': "PQRS",
'8': "TUV",
'9': "WXYZ",
}
鉴于此或任何其他d（可执行）伪代码，将一串数字转换为所有可能的字母串：
def digstolets(digs):
if len(digs) == 0:
yield ''
return
first, rest = digs[0], digs[1:]
if first not in d:
for x in digstolets(rest): yield first + x
return
else:
for x in d[first]:
for y in digstolets(rest): yield x + y
可根据您想要对输入字符串中不在之间的字符执行的操作进行调整2和9包含的字符执行的操作进行调整（此版本只是将它们呼应出来！-）。
例如，
print list(digstolets('1234'))
在这个版本中发出
['1ADG', '1ADH', '1ADI', '1AEG', '1AEH', '1AEI', '1AFG', '1AFH', '1AFI',
'1BDG', '1BDH', '1BDI', '1BEG', '1BEH', '1BEI', '1BFG', '1BFH', '1BFI',
'1CDG', '1CDH', '1CDI', '1CEG', '1CEH', '1CEI', '1CFG', '1CFH', '1CFI']
编辑：OP要求更多解释，这是一个尝试。函数digstolets（数字到字母）接受一串数字digs并产生可以是字母或“非数字”的字符串序列。 0并1在这里算作非数字，因为它们不会扩展为字母，就像空格和标点符号不会 - 仅包含的数字扩展2为9字母（在大多数情况下每种三种可能性，两种情况下四种可能性，因为7可以扩展为any ofPQRS并且9可以扩展到任何WXYZ)。
首先，基本情况：如果什么都不剩（字符串digs为空），唯一可能的结果是空字符串，仅此而已，这个递归调用完成，完成，kaput。
如果digs是非空的，它可以被分成一个“头”，第一个字符，和一个“尾”，所有其余的（第一个字符之后的 0 个或多个字符）。
如果不是数字，“头”要么保持在输出中，要么保持原样；或扩展到任何三种或四种可能性，如果是一个数字。在任何一种情况下，头部的一个、三个或四个可能的扩展都必须与尾部的每个可能的扩展连接起来——从那里递归调用，以获得尾部的所有可能的扩展（所以我们循环所有所说的可能尾部的扩展，并产生与尾部的每个可能扩展连接的头部的一个、三个或四个可能的扩展中的每一个）。然后，再一次，就是这样，伙计们。
我不知道如何用更基本的术语来表达这一点——如果在此之后 OP 仍然丢失，我只能建议对有关递归的所有内容进行认真、全面的审查。删除递归以支持显式维护的堆栈并不能简化这个概念性阐述——取决于所涉及的语言（很高兴听到 OP 完全熟悉哪些语言！），递归消除可能是一个重要的优化，但是这绝不是概念上的简化......！-)
于 2009-12-05T05:55:02.450 回答
2
Java的另一个版本。
首先，它根据电话号码的每个数字选择字符数组。然后使用递归它生成所有可能的排列。
public class PhonePermutations {
public static void main(String[] args) {
char[][] letters =
{{'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'}};
String n = "1234";
char[][] sel = new char[n.length()][];
for (int i = 0; i < n.length(); i++) {
int digit = Integer.parseInt("" +n.charAt(i));
sel[i] = letters[digit];
}
permutations(sel, 0, "");
}
public static void permutations(char[][] symbols, int n, String s) {
if (n == symbols.length) {
System.out.println(s);
return;
}
for (int i = 0; i < symbols[n].length; i ++) {
permutations(symbols, n+1, s + symbols[n][i]);
}
}
}
于 2012-05-19T13:38:27.983 回答
2
如果在采访中被问到这个问题，我会从分解问题开始。您必须解决哪些问题？
首先，您需要将一个数字映射到一组字母。一些数字将映射到不同数量的字母。因此，首先要弄清楚如何存储这些数据。基本上你想要一个数字到字母集合的映射。
一旦你到了那里，让它变得更容易，你将如何为一个 1 位数字生成所有“单词”？基本上如何遍历映射到给定数字的集合。有多少种可能性？
好的，现在下一步是，你有两个数字并且想要生成所有的单词。如果您只是手动执行此操作，您将如何执行此操作？您将从第一个数字的第一个字母开始，第二个数字的第一个字母开始。然后转到第二个数字的下一个字母，保留第一个字母的第一个字母，依此类推。将其视为数字（基本上索引到两个数字的集合中，每个数字映射到 3 个字母）：
00,01,02,10,11,12,20,21,22
那么如何在代码中生成该数字序列呢？
一旦你能做到这一点，把它翻译成代码应该是微不足道的。
祝你好运！
于 2009-12-06T05:10:03.027 回答
1
这是一个计数问题，因此通常有助于为较小的问题找到解决方案，然后考虑如何将其扩展到您的一般情况。
如果你有一个1位数的电话号码，会有多少种可能性？如果你有2位数怎么办？你是如何从一个移动到另一个的，你能想出一个解决n位数的方法吗？
于 2009-12-05T05:41:46.450 回答
1
这是我想出的：
import java.util.*;
public class PhoneMmemonics {
/**
* Mapping between a digit and the characters it represents
*/
private static Map<Character,List<Character>> numberToCharacters = new HashMap<Character,List<Character>>();
static {
numberToCharacters.put('0',new ArrayList<Character>(Arrays.asList('0')));
numberToCharacters.put('1',new ArrayList<Character>(Arrays.asList('1')));
numberToCharacters.put('2',new ArrayList<Character>(Arrays.asList('A','B','C')));
numberToCharacters.put('3',new ArrayList<Character>(Arrays.asList('D','E','F')));
numberToCharacters.put('4',new ArrayList<Character>(Arrays.asList('G','H','I')));
numberToCharacters.put('5',new ArrayList<Character>(Arrays.asList('J','K','L')));
numberToCharacters.put('6',new ArrayList<Character>(Arrays.asList('M','N','O')));
numberToCharacters.put('7',new ArrayList<Character>(Arrays.asList('P','Q','R')));
numberToCharacters.put('8',new ArrayList<Character>(Arrays.asList('T','U','V')));
numberToCharacters.put('9',new ArrayList<Character>(Arrays.asList('W','X','Y','Z')));
}
/**
* Generates a list of all the mmemonics that can exists for the number
* @param phoneNumber
* @return
*/
public static List<String> getMmemonics(int phoneNumber) {
// prepare results
StringBuilder stringBuffer = new StringBuilder();
List<String> results = new ArrayList<String>();
// generate all the mmenonics
generateMmemonics(Integer.toString(phoneNumber), stringBuffer, results);
// return results
return results;
}
/**
* Recursive helper method to generate all mmemonics
*
* @param partialPhoneNumber Numbers in the phone number that haven't converted to characters yet
* @param partialMmemonic The partial word that we have come up with so far
* @param results total list of all results of complete mmemonics
*/
private static void generateMmemonics(String partialPhoneNumber, StringBuilder partialMmemonic, List<String> results) {
// are we there yet?
if (partialPhoneNumber.length() == 0) {
//Printing the pnemmonics
//System.out.println(partialMmemonic.toString());
// base case: so add the mmemonic is complete
results.add(partialMmemonic.toString());
return;
}
// prepare variables for recursion
int currentPartialLength = partialMmemonic.length();
char firstNumber = partialPhoneNumber.charAt(0);
String remainingNumbers = partialPhoneNumber.substring(1);
// for each character that the single number represents
for(Character singleCharacter : numberToCharacters.get(firstNumber)) {
// append single character to our partial mmemonic so far
// and recurse down with the remaining characters
partialMmemonic.setLength(currentPartialLength);
generateMmemonics(remainingNumbers, partialMmemonic.append(singleCharacter), results);
}
}
}
于 2009-12-06T21:40:16.720 回答
0
使用递归和良好的数据结构来保存可能的字符。由于我们在谈论数字，因此数组数组可以工作。
char[][] toChar = {{'0'}, {'1'}, {'2', 'A', 'B', 'C'}, ..., {'9', 'W' ， 'X'。'Y'} };
请注意，此数组数组中的第 i 个数组包含与电话上第 i 个按钮相对应的字符。即，tochar[2][0] 是'2'，tochar[2][1] 是'A'，等等。
递归函数将索引作为参数。它将有一个 for 循环遍历替换字符，用数组中的一个替换该索引处的字符。如果长度等于输入字符串的长度，则输出该字符串。
在 Java 或 C# 中，您可能希望使用字符串缓冲区来保存更改的字符串。
function recur(index)
if (index == input.length) output stringbuffer
else
for (i = 0; i < tochar[input[index]].length; i++)
stringbuffer[index] = tochar[input[index]][i]
recur(index + 1)
于 2009-12-05T06:55:25.127 回答
0
C程序：
char *str[] = {"0", "1", "2abc", "3def", "4ghi", "5jkl", "6mno", "7pqrs", "8tuv", "9wxyz"};
const char number[]="2061234569";
char printstr[15];
int len;
printph(int index)
{
int i;
int n;
if (index == len)
{
printf("\n");
printstr[len] = '\0';
printf("%s\n", printstr);
return;
}
n =number[index] - '0';
for(i = 0; i < strlen(str[n]); i++)
{
printstr[index] = str[n][i];
printph(index +1);
}
}
称呼
printph(0);
于 2012-12-12T16:52:57.170 回答
0
我想到的一个问题是，0 和 1 在这样的系统中应该变成什么？否则，您所拥有的东西基本上可以递归地遍历 2-9 范围内的每个值的字母，以便以简单的蛮力方式生成所有值。
假设北美的电话号码长度正常，并且最初忽略特殊区号，还有一个问题是有多少位代表 4 个值而不是 3，因为 7 和 9 往往会得到那些经常不使用的字母 Q 和 Z，因为计数范围可能从3^10 = 59,049 到 4^10 = 1,048,576。后者是 1024 平方，我刚刚注意到。
于 2009-12-09T19:33:46.827 回答
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;
vector<string> finalres;
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:53:49.877 回答
0
OP 似乎在要求实现，因为他正在努力理解上面的伪代码。也许这个Tcl 脚本会有所帮助：
array set d {
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}
}
proc digstolets {digits} {
global d
set l [list]
if {[string length $digits] == 0} {
return $l
}
set first [string index $digits 0]
catch {set first $d($first)}
if {[string length $digits] == 1} {
return $first
}
set res [digstolets [string range $digits 1 end]]
foreach x $first {
foreach y $res {
lappend l $x$y
}
}
return $l
}
puts [digstolets "1234"]
于 2011-02-21T19:30:18.667 回答