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

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

4

6 回答 6

19

（我将此作为单独的答案添加，因为它处理问题的方式与我在第一期中提到的不同）

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

它使用因式分解来确定一个词是否是另一个词的字谜。它将做的是为每个字母分配一个唯一的主要值；您可以通过将所有值相乘来计算给定单词中字母的值。例如，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'
于 2012-05-18T14:03:32.343 回答
2

我不太明白你的代码在做什么；但如果你想要一个简单的字谜检查器，伪代码将类似于：

get array of letters in my anagram
for each word in the dictionary
    get array of letters in this word
    for each letter in my anagram
        is this letter also in the word?
            if no, move on to the next word
    if we get here, it's an anagram

您可以做一些额外的事情 - 您可以确保字谜和字典单词的长度相同（如果不是，它们就不能是字谜）；并且您还需要弄清楚如何处理字典单词中多次出现但在字谜词中只出现一次的字母（例如，上面的代码会将“aa”报告为“a”的字谜）

于 2012-05-17T15:10:08.173 回答
0

试试字符串洗牌功能？

str_shuffle ( string $str )

这是一些伪代码：

Get random string from array
store string copy (Not shuffled)
string shuffle another copy
echo shuffled string
get users guess
parse guess (Remove illegal characters)
if parsed guess = string
    reward
else
    ?let user try again?
于 2013-11-19T15:52:58.277 回答
0

我无法理解您的问题、您对代码的解释以及代码本身。您想检查任意单词是否是字典中某个单词的字谜？

这很简单——创建一个包含 26 个整数的数组。遍历小写的输入单词，为每个字母将 array[letter - 'a'] （或任何 php 等效项）增加 1。

然后遍历字典并为每个单词以相同的方式生成 array_dict，并检查 i = 0...25 if array[i] == array_dict[i]。如果它们都相同，则这些词是字谜。当然，在每个单词之后将 array_dict 设置回零。

另一种方法是对字符串中的字母进行排序，然后简单地比较排序后的字符串。如果允许您修改/预处理字典，这很好 - 您保持字典预先排序，然后只需对输入单词进行排序并将其与字典单词进行比较。最佳解决方案可能是创建一个（用 C# 术语，我不知道 php 抱歉） 

Dictionary<string, List<string>>

并通过对每个单词进行排序，在字典中查找它来预处理您的字典，如果列表不存在，则创建它，并在任何一种情况下将单词添加到列表中。然后，当用户输入单词时，您可以对其进行排序并返回 dictionary[sortedword] 作为结果 - 在基本恒定的时间内找到所有字谜（输入字符串长度为 nlogn，但字典大小为常数）。

于 2012-05-17T15:27:44.043 回答
0 
$dictionary = array("kayak");

$anagram = "kayak";

$anagramSorted = sortString($anagram);


foreach ($dictionary as $word)
{
    $wordSorted = sortString($word);
    if ($wordSorted == $anagramSorted)
    {
       echo 'true';
    }
}

function sortString($s)
{
    $chars = array();
    $length = strlen($s);
    for ($i=0;$i<$length;$i++)
    {
       $chars[] = $s[$i];
    }
    sort($chars);

    return implode("",$chars);
}
于 2012-05-17T15:58:04.147 回答
0

此函数将获取字符串并返回字符串中存在的计数字谜。

function countingAnagrams($str)
    {
        $str_arry = [];
        $anagrams = 0;
        $str_arry= explode(' ', $str);
        for ($i = 0; $i < count($str_arry); $i++) {
            $str_cmp = $str_arry[$i];
            for($k = 0; $k < count($str_arry); $k++){
                if($i != $k){
                    $str_rev = $str_arry[$k];
                    if (count_chars($str_cmp, 1) == count_chars($str_rev, 1))
                    {
                        unset($str_arry[$i]);
                        $str_arry = array_values($str_arry);
                        $anagrams++;
                    }
                }
            }
        }
        return $anagrams;
    }


echo  countingAnagrams('cars are residing on my arcs');
于 2020-03-07T10:42:43.900 回答