Swift Anagram检查器

Question

我正在尝试为swift构建一个anagram检查器.这是我的代码.如果您不知道anagram检查器检查两个字符串是否包含相同的字符,但顺序无关紧要.

func checkForAnagram(#firstString: String, #secondString: String) -> Bool {
    var firstStringArray: [Character] = []
    var secondStringArray: [Character] = []
    /* if case matters delete the next four lines
    and make sure your variables are not constants */
    var first = firstString
    var second = secondString
    first = first.lowercaseString
    second = second.lowercaseString
    for charactersOne in first {
        firstStringArray += [charactersOne]
    }
    for charactersTwo in second {
        secondStringArray += [charactersTwo]
    }
    if firstStringArray.count != secondStringArray.count {
        return false
    } else {
        for elements in firstStringArray {
            if secondStringArray.contains(elements){
                return true
            } else {
                return false
            }
        }

}
}


var a = "Hello"
var b = "oellh"
var c = "World"
checkForAnagram(firstString: a, secondString: b)

我收到一条错误消息.

'[Character]' does not have a member 'contains'

Answer 1

接受的答案是紧凑而优雅,但与其他解决方案相比效率非常低.

我现在将提出并讨论一些anagram检查器变体的实现.为了衡量性能,我将使用不同的变体来查找50,000多个单词数组中给定单词的字谜.

// Variant 1: Sorting of Character
// Measured time: 30.46 s
func anagramCheck1(a: String, b: String) -> Bool {
    return a.characters.sorted() == b.characters.sorted()
}

这基本上是用Swift 3语法编写的已接受答案的解决方案.它非常慢,因为与NSString不同,Swift的String基于Character,它可以正确处理Unicode字符.

一个更有效的解决方案是利用NSCountedSet类,它允许我们将字符串表示为一组字符,每个字符都有自己的计数.如果两个字符串映射到相同的NSCountedSet,则它们是字符串.注意:检查字符串长度作为前提条件会使实现始终更有效.

// Variant 2: NSCountedSet of Character
// Measured time: 4.81 s
func anagramCheck2(a: String, b: String) -> Bool {
    guard a.characters.count == b.characters.count else { return false }
    let aSet = NSCountedSet()
    let bSet = NSCountedSet()
    for c in a.characters {
        aSet.add(c)
    }
    for c in b.characters {
        bSet.add(c)
    }
    return aSet == bSet
}

更好,但不是很好.在这里,其中一个"罪魁祸首"是使用原生的Swift Character类型(来自Swift的String).回到旧的Objective-C类型(NSString和unichar)可以提高效率.

// Variant 3: NSCountedSet of unichar
// Measured time: 1.31 s
func anagramCheck3(a: String, b: String) -> Bool {
    let aString = a as NSString
    let bString = b as NSString
    let length = aString.length
    guard length == bString.length else { return false }
    let aSet = NSCountedSet()
    let bSet = NSCountedSet()
    for i in 0..<length {
        aSet.add(aString.character(at: i))
        bSet.add(bString.character(at: i))
    }
    return aSet == bSet
}

使用NSCountedSet很好,但在我们比较两个NSCountedSet对象之前,我们完全填充它们.一个有用的替代方法是仅为两个字符串中的一个完全填充NSCountedSet,然后,当我们为另一个字符串填充NSCountedSet时,如果另一个字符串包含在第一个字符串的NSCountedSet中找不到的字符,则我们会提前失败串.

// Variant 4: NSCountedSet of unichar and early exit
// Measured time: 1.07 s
func anagramCheck4(a: String, b: String) -> Bool {
    let aString = a as NSString
    let bString = b as NSString
    let length = aString.length
    guard length == bString.length else { return false }
    let aSet = NSCountedSet()
    let bSet = NSCountedSet()
    for i in 0..<length {
        aSet.add(aString.character(at: i))
    }
    for i in 0..<length {
        let c = bString.character(at: i)
        if bSet.count(for: c) >= aSet.count(for: c) {
            return false
        }
        bSet.add(c)
    }
    return true
}

这是我们将获得的最佳时机(使用Swift).但是,为了完整起见,让我再讨论一下这种变体.

下一个替代方案利用类型[unichar:Int]的Swift Dictionary来存储每个字符的重复次数,而不是NSCountedSet.它比前两个变体略慢,但我们可以稍后重用它以获得更快的实现.

// Variant 5: counting repetitions with [unichar:Int]
// Measured time: 1.36
func anagramCheck5(a: String, b: String) -> Bool {
    let aString = a as NSString
    let bString = b as NSString
    let length = aString.length
    guard length == bString.length else { return false }
    var aDic = [unichar:Int]()
    var bDic = [unichar:Int]()
    for i in 0..<length {
        let c = aString.character(at: i)
        aDic[c] = (aDic[c] ?? 0) + 1
    }
    for i in 0..<length {
        let c = bString.character(at: i)
        let count = (bDic[c] ?? 0) + 1
        if count > aDic[c] ?? 0 {
            return false
        }
        bDic[c] = count
    }
    return true
}

请注意,与Variant 3相对应的使用NSCountedSet的vanilla Objective-C实现比以前的所有版本都要快得多.

// Variant 6: Objective-C and NSCountedSet
// Measured time: 0.65 s
- (BOOL)anagramChecker:(NSString *)a with:(NSString *)b {
    if (a.length != b.length) {
        return NO;
    }
    NSCountedSet *aSet = [[NSCountedSet alloc] init];
    NSCountedSet *bSet = [[NSCountedSet alloc] init];
    for (int i = 0; i < a.length; i++) {
        [aSet addObject:@([a characterAtIndex:i])];
        [bSet addObject:@([b characterAtIndex:i])];
    }
    return [aSet isEqual:bSet];
}

我们可以改进之前尝试的另一种方法是观察,如果我们需要找到给定单词的字谜,我们不妨将该单词视为固定,因此我们可以构建相应的结构(NSCountedSet,Dictionary ,. ..)这个词只有一次.

// Finding all the anagrams of word in words
// Variant 7: counting repetitions with [unichar:Int]
// Measured time: 0.58 s
func anagrams(word: String, from words: [String]) -> [String] {
    let anagrammedWord = word as NSString
    let length = anagrammedWord.length
    var aDic = [unichar:Int]()
    for i in 0..<length {
        let c = anagrammedWord.character(at: i)
        aDic[c] = (aDic[c] ?? 0) + 1
    }
    let foundWords = words.filter {
        let string = $0 as NSString
        guard length == string.length else { return false }
        var bDic = [unichar:Int]()
        for i in 0..<length {
            let c = string.character(at: i)
            let count = (bDic[c] ?? 0) + 1
            if count > aDic[c] ?? 0 {
                return false
            }
            bDic[c] = count
        }
        return true
    }
    return foundWords
}

现在,在上一个版本中,我们使用[unichar:Int]字典计算.这证明比使用unichar的NSCountedSet更有效,无论是提前退出(0.60秒)还是没有(0.87秒).

Answer 2

你应该试试

func checkForAnagram(firstString firstString: String, secondString: String) -> Bool {
    return firstString.lowercaseString.characters.sort() == secondString.lowercaseString.characters.sort()
}