斯卡拉：使用素数的两个字符串的字谜

解决！斯卡拉：使用素数的两个字符串的字谜

我正在研究检查两个字符串是否为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

斯卡拉：使用素数的两个字符串的字谜

回答

相关问题