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...
?>

我希望算法尽可能简单,因为我完全是个新手.我很抱歉因为我的英语不太好.最诚挚的问候,Khiem Nguyen.

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

对于它的价值,我认为这是一个更优雅的解决方案 - 您可以通过预先计算字典中的值来加快速度.如果您查看字典中每个单词的因子,可以直接在数据库中进行搜索:

SELECT word FROM dictionary WHERE wordFactor='$factorOfThisWord'