2

我正在尝试打印可以从 php 中的电话号码形成的可能单词。我的一般策略是将每个数字映射到可能的字符数组。然后我遍历每个数字，递归调用函数来遍历每个可能的字符。

这是我的代码到目前为止的样子，但它还没有成功。我可以进行任何语法更正以使其正常工作吗？

$pad = array(
        array('0'), array('1'), array('abc'), array('def'), array('ghi'),
        array('jkl'), array('mno'), array('pqr'), array('stuv'), array('wxyz')    
);   

function convertNumberToAlpha($number, $next, $alpha){

    global $pad;
    for($i =0; $i<count($pad[$number[$next]][0]); $i++){
        $alpha[$next] = $pad[$next][0][$i];

        if($i<strlen($number) -1){
            convertNumberToAlpha($number, $next++, $alpha);
        }else{
            print_r($alpha);
        }
    }    
}


$alpha = array();
convertNumberToAlpha('22', 0, $alpha);
4

3 回答 3

3

这将如何使用？这不是您所建议的简单递归算法的工作，甚至不是迭代方法。平均 10 位数字将产生 59,049 (3^10) 种可能性，如果您想确定实际单词，则必须根据字典对每种可能性进行评估。

很多时候，最好的方法是预编译一个字典，将 10 位数字映射到各种单词。然后，您的查找是一个常数 O(1) 算法，只需选择一个 10 位数字，该数字映射到一个可能的单词数组。

事实上，预编译字典是 T9 的工作方式，将字典映射到具有对数查找函数的树。

于 2013-01-26T20:01:25.160 回答
1

下面的代码应该做到这一点。相当直接：它使用递归，每个级别处理一个输入字符，在每次递归调用时构建/传递当前组合的副本，递归在处理输入的最后一个字符的级别停止。

function alphaGenerator($input, &$output, $current = "") {
    static $lookup = array(
        1 => "1",    2 => "abc", 3 => "def",
        4 => "ghi",  5 => "jkl", 6 => "mno",
        7 => "pqrs", 8 => "tuv", 9 => "wxyz",
        0 => "0"
    );
    $digit = substr($input, 0, 1);          // e.g. "4"
    $other = substr($input, 1);             // e.g. "3556"
    $chars = str_split($lookup[$digit], 1); // e.g. "ghi"
    foreach ($chars as $char) {             // e.g. g, h, i
        if ($other === false) {             // base case
            $output[] = $current . $char;
        } else {                            // recursive case
            alphaGenerator($other, $output, $current . $char);
        }
    }
}
$output = array();
alphaGenerator("43556", $output);
var_dump($output);

输出：

array(243) {
  [0]=>string(5) "gdjjm"
  [1]=>string(5) "gdjjn"
  ...
  [133]=>string(5) "helln"
  [134]=>string(5) "hello"
  [135]=>string(5) "hfjjm"
  ...
  [241]=>string(5) "iflln"
  [242]=>string(5) "ifllo"
}
于 2013-01-26T20:58:41.480 回答
0

您应该阅读 Norvigs 关于用 Python 编写拼写检查器的文章http://norvig.com/spell-correct.html。虽然它是一个拼写检查器，并且在 python 中不是 php，但它是围绕查找可能变化的单词的相同概念，可能会给你一些好主意。

于 2013-01-26T20:05:01.280 回答