Анаграмма в Свифте

Эта статья также опубликована в моем блоге: https://truongnn.me/2019/03/20/anagram-in-swift/

Контент

• "Введение"
• Практический пример: Проверить, являются ли две строки анаграммами друг друга
• Решение 1
• Решение 2

ВВЕДЕНИЕ

Две строки являются анаграммами, если они используют одни и те же символы в одинаковом количестве. Мы проверяем только символы, игнорируя пробелы и строчные/верхние регистры.

Например:

• «abc def» против «fde cba» ====› true
• «abc» vs «a» ====› false (должна быть одинаковой длины)
• «abc» vs «a b c» true (без учета пробела)
• «abc» vs «A b c» true (игнорировать пробел, верхний регистр не имеет значения)

ПРАКТИЧЕСКИЙ ПРИМЕР: ПРОВЕРИТЬ, ЯВЛЯЮТСЯ ЛИ ДВЕ СТРОКИ АНАГРАМАМИ ДРУГ ДРУГА

РЕШЕНИЕ 1:

Поскольку нам нужно найти символ из строки внутри другой строки, также убедитесь, что количество вхождений этого символа одинаково в обеих строках. Итак, давайте воспользуемся структурой данных, которая поможет нам быстро найти элемент: Словарь.

Для каждой строки мы создаем словарь, в котором хранится символ (ключ) и количество вхождений этого символа (значения) внутри строки, давайте реализуем его как расширение строки:

public extension String {        
    /**
     Build a Dictionary with Key is a String, Value: Key's number of occurrence in the current string.
     - Returns:
        - a Dictionary with Key is a String, Value: Key's number of occurrence in the current string.
     */
    func stringMap() -> [String: Int] {
        var result = [String: Int]()
        for character in self {
            if let count = result[String(character)] {
                result[String(character)] = count + 1
            } else {
                result[String(character)] = 1
            }
        }
        return result
    }
}

Напишите модульный тест для метода stringMap():

//MARK: test stringMap method
    func test_stringMap_whenStringIsNotEmpty_shouldReturnDictionary() {
        let stringTest = "abcd dba kil"
        let result = stringTest.stringMap()
        XCTAssertTrue(result["a"] == 2)
        XCTAssertTrue(result["b"] == 2)
        XCTAssertTrue(result["c"] == 1)
        XCTAssertTrue(result["d"] == 2)
        XCTAssertTrue(result["k"] == 1)
        XCTAssertTrue(result["i"] == 1)
        XCTAssertTrue(result["l"] == 1)
    }

Входными данными для метода stringMap должна быть строка без пробелов, все символы должны быть в нижнем регистре, давайте реализуем метод cleanString() внутри расширения String:

/**
     Create a string which contains lowercase, removes space.
     - Returns:
        - a string which contains lowercase, removes space.
     */
    func cleanString() -> String {
        return self.replacingOccurrences(of: " ", with: "").lowercased()
    }

Напишите модульный тест для метода cleanString():

//MARK: test cleanString method
    func test_cleanString_whenStringContainsCharatersAndSpace_shouldReturnStringContainsCharactersInLowercaseRemoveAllSpace() {
        let testString = "a b c d e 1 234"
        XCTAssertTrue(testString.cleanString() == "abcde1234")
    }
    
    func test_cleanString_whenStringContainsOnlySpaces_shouldReturnStringRemoveAllSpaces() {
        let testString = "           "
        XCTAssertTrue(testString.cleanString() == "")
    }

Хорошо, теперь мы можем реализовать метод anagram() внутри расширения String:

/**
     Check to see if two strings anagram of each other. Only check characters inside string, ignore space, lowercase & uppercase
     - Parameters:
        - string: a string that need to check anagrams with the target
     - Returns:
        - False: Two strings are not anagram each other
        - True: Two strings are anagrams each other
     */
    func anagram(string: String) -> Bool {
        let stringMap1 = cleanString().stringMap()
        let stringMap2 = string.cleanString().stringMap()
        if stringMap1.keys.count != stringMap2.keys.count {
            return false
        }
        for character in self {
            if stringMap1[String(character)] != stringMap2[String(character)] {
                return false
            }
        }
        return true
    }

Мы сравниваем количество ключей в каждом словаре, чтобы убедиться, что обе строки используют одинаковый набор символов.

Для этого решения нам нужно зациклить все символы внутри каждой строки, чтобы построить [String: Int], если две строки используют один и тот же набор символов, нам нужно снова зациклить одну из них, чтобы найти символ внутри другой строки.

Это так много шагов. Это решение работает хорошо. Но я думаю, что мы можем придумать другое решение, простое для понимания: Решение 2.

РЕШЕНИЕ 2

Это просто: для каждой строки преобразовать ее в массив, отсортировать этот массив, преобразовать этот массив в строку

Сравните эти строки результатов

Реализация:

/**
     Check to see if two strings anagram of each other. Only check characters inside string, ignore space, lowercase & uppercase
     - Parameters:
        - string: a string that need to check anagrams with the target
     - Returns:
        - False: Two strings are not anagram each other
        - True: Two strings are anagrams each other
     */
    func anagram(string: String) -> Bool {
        let sortedString1 = String(Array(self.cleanString()).sorted())
        let sortedString2 = String(Array(string.cleanString()).sorted())
        return sortedString1 == sortedString2
    }

Как видите, это проще для понимания, чем Решение 1.

Напишем для этого тесты:

//MARK: test anagrams method
    func test_anagrams_withTwoStringsAreAnagramsEachOther_shouldReturnTrue() {
        let testString1 = "abcdef gh"
        let testString2 = "gh dcbaef"
        XCTAssertTrue(testString1.anagram(string: testString2))
        XCTAssertTrue("        abc".anagram(string: "a b c"))
    }
    
    func test_anagrams_withTwoStringsAreNotAnagramsEachOther_shouldReturnFalse() {
        let testString1 = "abcdef gh"
        let testString2 = "Truong Nguyen"
        XCTAssertFalse(testString1.anagram(string: testString2))
        
        let testString3 = "abcdef gh123"
        XCTAssertFalse(testString1.anagram(string: testString3))
let testString4 = " "
        XCTAssertFalse(testString1.anagram(string: testString4))
        
        XCTAssertFalse("abc".anagram(string: "a"))
    }
    
    func test_anagrams_withTwoStringsAreEmpty_shouldReturnTrue() {
        let testString1 = ""
        let testString2 = ""
        XCTAssertTrue(testString1.anagram(string: testString2))
    }

Что вы думаете? Дайте мне знать ваши вопросы и дайте мне обратную связь:

Скайп: nhutruongit88

Электронная почта: [email protected]

Спасибо за чтение!