php - PHP 中的 Anagram 算法

Question

我完全是 PHP 新手。今天我遇到了一个我不知道如何解决的问题，即使在搜索谷歌和挖掘 SOF 之后也是如此。这是 Anagram 算法。

所以基本上，我理解这里的问题:当用户输入一个字符串时，我将它拆分并与我的库(给定数组)进行比较，然后我将不得不通过 2-3-...等字符加入它以再对比一下，正是我现在卡住的地方，我不知道如何加入数组的元素。

这是我正在实现的代码，还有一个示例字典。

我有一个自制的字典，其中包含数组 $dict 中的这些元素。我有一个表单供用户输入字符串，输入的字符串将传递给下面的代码并声明为 $anagram。我必须拆分输入的字符串以与我的字典进行比较。但是我不知道如何加入他们，比如比较 2 个字母，3 个字母......等等......等等，到字典。

<?php

$dict = array(
'abde',
'des',
'klajsd',
'ksj',
'hat',
'good',
'book',
'puzzle',
'local',
'php',
'e');

$anagram = $_POST['anagram'];
//change to lowercase
$anagram = strtolower($anagram);

//split the string
$test = str_split($anagram);

//compare with $dict for the first split without joining
for ($i=0; $i<strlen($anagram); $i++) {
    if ($test[$i]==$dict[$i]) {
        echo $test[$i]."<br />";
    }
}

//problem: how to join elements of the array in the loops
//like user inputs "hellodes"
//after echo "e", how to join the elements like: h-e,h-l,h-l,h-o,h-d,h-e,h-s
//and then h-e-l,h-e-l,h-e-o...etc...
?>

我希望算法尽可能简单，因为我完全是个新手。对不起，因为我的英语不太好。 最好的祝福， 阮谦。

Answer 1

(我将其添加为一个单独的答案，因为它与我在第一期中提到的处理问题的方式不同)

这是一种更复杂的方法，可以确定字典中的哪些单词是您要查找的单词的一部分；我会留给读者去弄清楚它是如何工作的。

它使用因式分解来计算一个词是否是另一个词的变位词。它会做的是为每个字母分配一个唯一的素数；您可以通过将所有值相乘来计算给定单词中字母的值。例如，CAT 是 37 * 5 * 3，即 510。如果您的目标词分解为相同的数字，则可以确定一个是另一个的变位词。

我按照素数在英式英语中的常见程度对素数进行排序，以使生成的因数更小。

<?php

function factorise($word)
{
    // Take a number, split it into individual letters, and multiply those values together
    // So long as both words use the same value, you can amend the ordering of the factors 
    // as you like

    $factors = array("e" => 2, "t" => 3, "a" => 5, "o" => 7, "i" => 11,
        "n" => 13, "s" => 17, "h" => 19, "r" => 23, "d" => 29,
        "l" => 31, "c" => 37, "u" => 41, "m" => 43, "w" => 47,
        "f" => 53, "g" => 59, "y" => 61, "p" => 67, "b" => 71,
        "v" => 73, "k" => 79, "j" => 83, "x" => 89, "q" => 97,
        "z" => 101);

    $total = 1;

    $letters = str_split($word);

    foreach ($letters as $thisLetter) {
        if (isset($factors[$thisLetter])) {
            // This will skip any non-alphanumeric characters.
            $total *= $factors[$thisLetter];
        }
    }

    return $total;
}

$searchWord = "hasted";

$dict = array("abde", "des", "klajsd", "ksj", "hat", "hats");

$searchWordFactor = factorise($searchWord);

foreach ($dict as $thisWord) {
    // Factorise each word that we're looking for
    // If the word we've just factored is an exact divisor of the target word, then all the 
    // letters in that word are also present in the target word
    // If you want to do an exact anagram, then check that the two totals are equal

    $dictWordFactor = factorise($thisWord);

    if (($searchWordFactor % $dictWordFactor) == 0) {
        print ($thisWord . " is an anagram of " . $searchWord . "<br/>");
    }
}

就其值(value)而言，我认为这是一个更优雅的解决方案 - 您可以通过预先计算字典中的值来加快速度。如果你遍历并计算出字典中每个单词的因素，你可以直接在数据库中进行搜索:

SELECT word FROM dictionary WHERE wordFactor='$factorOfThisWord'