PHP中的Anagram算法

发布时间：2020-12-13 22:19:15 所属栏目：PHP教程来源：网络整理

导读：我完全是 PHP的新手.今天我遇到了一个我不知道如何解决的问题,即使在搜索谷歌和挖掘SOF之后.这是Anagram算法. 所以基本上,我理解这里的问题：当用户输入一个字符串时,我将它拆分并与我的库(一个给定的数组)进行比较,然后我将必须通过2-3 -…等字符加入它再次

我完全是 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-o,h-d,h-e,h-s
//and then h-e-l,h-e-l,h-e-o...etc...
?>

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

解决方法

(我将此作为单独的答案添加,因为这是处理问题的一种不同方式,而不是我在第一期中提到的)

这是一种更复杂的方法,可以解决字典中哪些单词是您正在寻找的单词的一部分;我会让读者知道它是如何工作的.

它使用因子分解来判断一个单词是否是另一个单词的字谜.它将做的是为每个字母分配一个独特的主要价值;您可以通过将所有值相乘来计算给定单词中字母的值.例如,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'

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!