PHP中的Anagram算法

Question

我完全是PHP的新手。今天，我遇到了一個問題，即使在搜索谷歌和挖掘SOF後，我也無法解決問題。這是Anagram算法。

所以基本上，我明白這裏的問題：當用戶輸入一個字符串，我分裂它，並與我的庫（給定的數組）比較，那麼我將不得不通過2-3 -...等字符再次比較，這正是我現在被卡住的地方，我不知道如何加入數組的元素。

這是我正在實施的代碼，也是一個示例字典。

我有一個自制的字典，這些元素在數組$ dict中。而且我有一個供用戶輸入字符串的表單，輸入的字符串將被傳遞給下面的代碼並聲明爲$ anagram。我必須將輸入的字符串拆分爲與我的字典進行比較。但我不知道如何將它們加入字典中，比如比較兩個字母，三個字母等等等等。

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

Answer 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 

有一些額外的事情你可以做 - 你可以確保兩個字謎和字典單詞的長度相同（如果他們不是，他們不能成爲anagrams）;你還需要弄清楚如何處理在字典中多次出現的字母，但在字謎詞中只能出現一次（例如，上面的代碼會將'aa'報告爲'a'的字謎）

Answer 3

我無法理解您的問題，您對代碼和代碼本身的解釋。你想檢查一個任意的單詞是否是字典中的某個單詞的一個詞組？

這很簡單 - 製作一個26個整數的數組。以小寫字母輸入輸入單詞，每個字母增加數組[字母'a']（或任何php等價物）。

然後通過字典併爲每個單詞生成array_dict以相同的方式，並檢查i = 0 ... 25 if array [i] == array_dict [i]。如果它們都一樣，那麼這些詞就是變形詞。當然，在每個單詞之後將array_dict設置回零。

另一種方法是對字符串中的字母進行排序，並簡單比較排序後的字符串。如果您允許修改/預處理字典，那麼這種方法很好 - 您可以對字典進行預先排序，然後對輸入字進行排序並將其與字典中的字進行比較。最佳的解決方案可能會創建一個（在C＃中的術語，我不知道PHP對不起）

Dictionary<string, List<string>> 

和預處理你的字典裏通過排序每個單詞，看它在字典中，如果列表沒有按」 t存在創建它，並在任何情況下將該單詞添加到列表中。然後，當用戶輸入單詞時，可以對它進行排序並返回詞典[sortedword]作爲結果 - 所有在基本常量時間內找到的字典（輸入字符串長度爲nlogn，但字典大小不變）。

Answer 4

$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); 
} 

Answer 5

嘗試字符串shuffle函數？

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?