Anagrams in Swift with wildcard (or joker)

Question

Based on this function in Swift:

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
}

I'm trying to get this working with wildcard, but it doesn't. How can I check with ? or _ ?

Edit:

This is how it work :

input : anagrams(word: "MILK", from: ["EGGS", "MILK", "LINK", "LIMK", "TREE"])
output : ["MILK", "LIMK"]

I would like to work with wildcards, for example :

input : anagrams(word: "?ILK", from: ["EGGS", "MILK", "LINK", "LIMK", "TREE"])
output : ["MILK", "LINK", "LIMK"]

Why are you using `NSString` in Swift? A Swift string has much better support for getting individual characters than `NSString` does. — rmaddy, Sep 28 '18 at 15:42
Please [edit] your question (no comments) to include sample input and expected output. Clearly indicate what isn't working. And show your attempt to work with your wildcards. — rmaddy, Sep 28 '18 at 15:43

ielyamani · Accepted Answer · 2018-09-30T11:18:50.663

You could use this:

func anagrams(word: String, from words: [String]) -> [String] {
    let characterCount = word.count
    let histogramOfWord = histogram(of: word)
    let foundWords = words.filter { otherWord in
        //Exit early if the character counts differ
        if otherWord.count != characterCount {
            return false
        }

        let h2 = histogram(of: otherWord)

        //If they have similar histograms, count that word in
        if h2 == histogramOfWord {
            return true
        } 

        //Compare the histograms with wildcards taken into consideration
        else {
            guard let wildCards = histogramOfWord["?"], wildCards > 0 else {
                return false
            }

            let numberOfDifferences: Int = h2.map { entry in
                let key = entry.key
                let value1 = histogramOfWord[key] ?? 0
                let value2 = entry.value
                let difference = value2 - value1
                return difference >= 0 ? difference : 0
                }.reduce(0, +)

            return numberOfDifferences == wildCards
        }
    }
    return foundWords
}

It calls this function that calculates the frequencies of each character in a string:

func histogram(of string: String) -> [Character:Int] {
    var dictionary: [Character:Int] = [Character:Int]()
    for i in 0..<string.count {
        let c = string[string.index(string.startIndex, offsetBy: i)]
        dictionary[c] = (dictionary[c] ?? 0) + 1
    }
    return dictionary
}

And you could use it like so:

print(anagrams(word: "MILK", from: ["EGGS", "MILK", "LINK", "LIMK", "TREE"]))
//["MILK", "LIMK"]

print(anagrams(word: "?ILK", from: ["EGGS", "MILK", "LINK", "LIMK", "TREE"]))
//["MILK", "LINK", "LIMK"]

print(anagrams(word: "TREE?", from: ["ARETE", "BERET", "BARTE", "MILKA"]))
//["ARETE", "BERET"]

print(anagrams(word: "TREE", from: ["ATRE", "CRET", "LINK", "RETE", "TREE"]))
//["RETE", "TREE"]

Your solution is working well with wildcard but when there is 2 times the same letter it take it as wildcard. for example print(anagrams(word: "TREE", from: ["ATRE", "CRET", "LINK", "RETE", "TREE"])) will output ["ATRE", "CRET", "RETE", "TREE"] — Fabien Maurice, Sep 30 '18 at 06:26
@FabienMaurice I've updated the answer. If this answer solved your problem please upvote or/and mark it as accepted by clicking the check mark next to the answer. see: [How does accepting an answer work?](https://meta.stackexchange.com/a/5235) for more information — ielyamani, Sep 30 '18 at 07:54
Thanks @Carpsen90, it’s very close to what I’m looking for, but still have a small problem with 2 times the same letters and wildcard and in the same time. Exemple : print(anagrams(word: "TREE?", from: ["ARETE", "BERET", "BARTE", "MILKA"])) output: ["ARETE", "BERET", "BARTE"] (the last one BARTE should not be there) — Fabien Maurice, Sep 30 '18 at 11:00
@FabienMaurice I've updated the answer. I hope it is clear by now and that you could modify it for your future requirements. — ielyamani, Sep 30 '18 at 11:20
The histogram function can be implemented easier, compare `func characterCounts` in https://stackoverflow.com/a/52329293/1187415. — Martin R, Oct 01 '18 at 04:40
@MartinR isn't that a beauty! Thank you for expanding my life, again — ielyamani, Oct 01 '18 at 10:29

Anagrams in Swift with wildcard (or joker)

1 Answers1