F#：测试两个字符串是否是变位词

Question

我是编程新手，F# 是我的第一语言。

这是我的代码：

let areAnagrams (firstString: string) (secondString: string) =
    let countCharacters (someString: string) =
        someString.ToLower().ToCharArray() |> Array.toSeq
                                           |> Seq.countBy (fun eachChar -> eachChar)
                                           |> Seq.sortBy (snd >> (~-))
    countCharacters firstString = countCharacters secondString

let testString1 = "Laity"
let testString2 = "Italy"
printfn "It is %b that %s and %s are anagrams." (areAnagrams testString1 testString2) (testString1) (testString2)

这是输出：

It is false that Laity and Italy are anagrams.

出了什么问题？我应该做哪些改变？

Answer 1

您的 countCharacters 实现仅使用第二个元素（每个字符出现的次数）对元组进行排序，但如果有多个字符出现相同次数，则顺序不对定义。

如果你运行你的两个样本的countCharacters函数，你可以看到问题：

> countCharacters "Laity";;
val it : seq<char * int> = seq [('l', 1); ('a', 1); ('i', 1); ('t', 1); ...]
> countCharacters "Italy";;
val it : seq<char * int> = seq [('i', 1); ('t', 1); ('a', 1); ('l', 1); ...]

一种解决方案是仅使用 Seq.sort 并使用字母代码和出现次数对元组进行排序。

另一个问题是您正在比较两个 seq<_> 值并且这不使用结构比较，因此您需要将结果转换为列表或数组（已完全计算的东西） :

let countCharacters (someString: string) =
    someString.ToLower().ToCharArray() 
    |> Seq.countBy (fun eachChar -> eachChar)
    |> Seq.sort
    |> List.ofSeq

请注意，您实际上并不需要 Seq.countBy - 因为如果您只是对所有字符进行排序，它会同样有效（重复的字符只是一个接一个）。所以你可以只使用：

let countCharacters (someString: string) =
    someString.ToLower() |> Seq.sort |> List.ofSeq

Answer 2

对两个字符串的字符进行排序是一个简单的解决方案，但这可能是递归的一个很好的例子。

您可以立即排除不同长度的字符串。

您还可以过滤掉每次迭代中出现的所有字符，方法是将它们替换为空字符串。

let rec areAnagram (x:string) (y:string) =
    if x.Lenght  <> t.Lenght 
    then false else
    if x.Lenght = 0
    then true else 
    let reply = x.[0].ToString ()
    areAnagram
        (x.Replace (reply,""))
        (y.Replace (reply,""))

对于许多用例，以上应该比排序更快。

无论如何，我们可以更进一步，将其转换为快速整数排序，无需递归和字符串替换

let inline charToInt c = 
    int c - int '0'
let singlePassAnagram (x:string) =
    let hash : int array = Array.zeroCreate 100
    x |> Seq.iter (fun c->
    hash.[charToInt c] <- (hash.[charToInt c]+1)
    )  
let areAnagramsFast 
        (x:string) (y:string) =
    if x.Length <> y.Length
    then false else
    (singlePassAnagram x) = 
        (singlePassAnagram y)

这是一个fiddle

F#：测试两个字符串是否是变位词

F#: Testing whether two strings are anagrams

f#