Получить первый индекс в пользовательской функции «indexOf» в Swift 4

Question

Я изучаю Swift, и я получил эту задачу, чтобы улучшить свое обучение с помощью extensions

Создайте пользовательскую функцию «indexOf», которая возвращает первый индекс вхождения вданная строкаВходные данные могут быть смешанными

Таким образом, приведенное выше означает:

Text: "Hello, world"
Phrase: "lol"
Output: 2

Другой пример:

Text: "Hello, playground"
Phrase: " pal,ol"
Output: 2

Пояснение

Первый пример, когда phrase переставлен, может принимать следующие значения (по два раза из-за повторяющихся L):

llo
oll
lol

Таким образом, одна из перестановок фактически является частью слова Hello, начиная с индекса 2.

То же самое относится и ко второму примеру, он начинается с пробела, имеет ol в конце, которые фактически являются частью lo в первом слове, затем он имеет pal, который являетсяПерестановка pla.

У меня были разные способы решения этой проблемы:

1. Выполнение всех перестановок для каждой данной фразы и поиск каждой из них, оИсходный текст, однако проблемы, с которыми я сталкиваюсь при таком подходе, состоят в том, что число перестановок задается как N!, где N - количество букв во фразе, которые могут легко исчерпать память.

2. Ищем каждое письмо и сохраняем всеих позиции в исходном тексте внутри Dictionary [Character : [Int]], затем преобразуйте значения в массив массивов целых чисел ([[Int]]), чтобы мы могли отсортировать значения внутри и иметь возможность сравнивать их.Я использую этот подход, поскольку он кажется разумным решением, однако я застрял в том, как сравнивать значения в массиве или словаре с другими ...

Например, я использую следующий код:

import UIKit

var str = "Hello, playground"

extension String {
    func customIndexOf(subword: String) -> Int {
        var lettersDictionary: [Character : [Int]] = [ : ]
        var listOfIndexes: [[Int]] = []

        for letter in subword {
            lettersDictionary[letter] = findAllOccurrencesBy(letter: letter)
        }

        for (_, v) in lettersDictionary {
            listOfIndexes.append(v)
        }

        print(listOfIndexes)

        return -1
    }

    private func findAllOccurrencesBy(letter: Character) -> [Int] {
        var indexes = [Int]()
        var searchStartIndex = self.startIndex

        while searchStartIndex < self.endIndex,
            let range = self.range(of: String(letter), range: searchStartIndex..<self.endIndex),
            !range.isEmpty
        {
            let index = distance(from: self.startIndex, to: range.lowerBound)
            indexes.append(index)
            searchStartIndex = range.upperBound
        }

        return indexes
    }

    private func compareIndexes(listOfIndexes: [[Int]]) {

    }
}

print (str.customIndexOf(subword: "play"))

, который дает мне следующий вывод:

[[7], [9], [10], [2, 3, 8]]
-1

Это должно вернуть 7, потому что это гдеp из playground находится, поэтому я хочу пройтись по каждому из массивов и сравнить их со всеми остальными.Если разница между ними равна 1, это означает, что все буквы являются последовательными (что мы и хотим), если они есть, то мы возвращаем самый низкий индекс, в противном случае, если есть разница 2+ среди букв, которые мы возвращаем -1.

Как мне перебрать все массивы и посмотреть на разницу между индексами?Или есть более простой способ решить эту проблему?

Answer 1

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

Что если бы мы могли сравнивать две строки независимо от порядка вместо проверки всех перестановок?Если бы мы могли создать функцию, которая могла бы возвращать true, если в двух строках одинаковое количество букв, нам не понадобились бы все перестановки.Давайте назовем эту функцию funA (String) -> Bool

Затем мы можем вызвать эту функцию для движущегося индекса в строке, с которой мы проверяем (или в случае расширения self)

Пример:

Текст: Hello there
Фраза: lol
Начальный индекс: 0, длина: 3

funA(Hel) = false  
funA(ell) = false  
funA(llo) = true  

return 2, который является текущим начальным индексом