Анаграммы в Swift с подстановочными знаками (или джокером) - PullRequest
Новая
       10

Анаграммы в Swift с подстановочными знаками (или джокером)

0 голосов
/ 28 сентября 2018

На основе этой функции в 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
}

Я пытаюсь заставить это работать с подстановочными знаками, но это не так.Как я могу проверить с помощью ? или _?

Редактировать:

Вот как это работает: 

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

Я бынравится работать с подстановочными знаками, например: 

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

1 Ответ

0 голосов
/ 29 сентября 2018

Вы можете использовать это: 

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
}

Вызывает эту функцию, которая вычисляет частоты каждого символа в строке: 

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
}

И вы можете использовать это так: 

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"]
...