斯卡拉：使用素數的兩個字符串的字謎

我正在研究檢查兩個字符串是否爲anagrams的函數。簡單的版本將兩個字符串轉換爲一個CharArray，對它們進行排序並比較兩個數組。這是有效的，因爲Anagrams一旦排序就有相同順序的字母。例如，神，狗都整理上面編寫的「危險品條例」

def isAnagram2(s : String , t : String) : Boolean = { 
    if(s == null || t == null || s.length != t.length) false 

val str1: Array[Char] = s.toCharArray 
val str2: Array[Char] = t.toCharArray 
sort(str1) 
sort(str2) 
    equals(str1, str2)

}

守則和工作在斯卡拉2.10.The輸出：

apple, papel: true 
carrot, tarroc: true 
hello, llloh: false 
abba, xyzz: false

然而，這是由於排序兩次需要很長的字符串，因此效率不高。根據此文章：Comparing anagrams using prime numbers。

爲字符檢查兩個字符串的最快方法是使用素數作爲哈希函數。

的主要思想是：

假設兩個字符串的相同lenght ...

1）生成哈希使用簡單的替換爲每個字符即乙 - > 3

2）乘以所有hashvalues因爲素數乘法獨特

3）比較StringA的黃金哈希StringB

如果兩個字符串具有相同的長度並且由相同的字符組成，則它們應該具有相同的素數散列。

例如 '貓' 和 '行爲' 想

sum_act = INT（A）+ INT（C） sum_cat = INT（C）+ INT（a）中

所以sum_act = = sum_cat

要點是，這個版本是獨立於順序的，因此不需要排序並且每個字符都有不變的查找時間。

在實踐中，我有一個對象PrimeHash：

object PrimeHash{ 
private[this] final val primeAlphabet: Map[Char, Int] = Map('a' -> 2, 'b' .., 'z' -> 101) 

def hashOf(string : String): Int = { 
    string.trim().toLowerCase.foldLeft(1) { (hash, c) => hash * primeAlphabet(c)} 
    } 
}

，並使用hashOf功能，像這樣：

def isAnagram(s : String , t : String) : Boolean ={ 
    if(s == null || t == null || s.length != t.length) false 
    else if(PrimeHash.hashOf(s).equals(PrimeHash.hashOf(t))) true 
    else false 
}

但是，我簡單的測試用例未能檢測到非字謎遊戲。這裏是測試代碼：

def main(args: Array[String]): Unit = { 

val pairs = Array(Array("apple", "papel"), Array("carrot", "tarroc"),Array("hello", "llloh"),Array("abba", "xyzz")) 

for(p <- pairs){ 
    val word1 = p(0) 
    val word2 = p(1) 
    val anagram = isAnagram2(word1, word2) 
    println(word1 + ", " + word2 + ": " + anagram) 
} 
}

排序功能正確地檢測到兩個「錯誤」對，但不是散列一個。在github上

全碼：https://gist.github.com/marvin-hansen/9953592

我不能完全肯定是否hashOf功能正確

解決方案：導致比較hashof相同的值（T）的自身固定式。感謝mesutozer。

來源

2014-04-03 Marvin.Hansen

你有一個錯字：比較hashof相同的值（T）

else if(PrimeHash.hashOf(t).equals(PrimeHash.hashOf(t))) true

來源

2014-04-03 12:55:39 mesutozer

感謝您的權利，雙重檢查一遍它的作品吧！ –

爲我工作的其他測試字符串..讓我試試其他人 – mesutozer

您是否認爲，這將適用於大型數據集。如8 + 2 = 10和5 + 5 = 10。因此對於大數據集可能是兩個相等的字符串將具有相同的長度和總和但不同的字符 – Sam

斯卡拉：使用素數的兩個字符串的字謎

回答

相關問題