arrays - 在 Swift 4 的自定义 "indexOf"函数中获取第一个索引

Question

我正在学习 Swift，我接受了这个挑战，以便通过 extensions

提高我的学习水平

Create a custom "indexOf" function that returns the first index of the occurrence in a given String. Input can be mixed

所以上面的翻译为:

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 因为那是 playground 的 p 所在的位置，所以我想遍历每个数组并比较它们反对所有其他人。如果它们之间的差异为 1，则表示字母都是连续的(这正是我们想要的)，如果它们是连续的，则返回最低索引，否则如果字母之间的差异为 2+，则返回 -1。

如何遍历所有数组并查找索引之间的差异？或者有没有更简单的方法来解决这个问题？

Answer 1

你的扩展语法很好，所以你需要改进你的算法逻辑。将其分解为两个更简单的问题:检查子字符串中的字符串，以及检查字符串是否匹配字符串的排列

如果我们可以不考虑顺序地比较两个字符串而不是检查所有排列会怎样？如果我们可以创建一个函数，只要两个字符串出现相同的字母就可以返回 true，那么我们就不需要所有的排列。我们称这个函数为 funA(String) -> Bool

然后我们可以在我们正在检查的字符串中的移动索引上调用该函数(或者在扩展的情况下，self)

例子:

文字:你好
短语:哈哈
起始索引:0，长度:3

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

返回2，也就是当前的起始索引