从字符串数组中找到最常见的子字符串

Question

我想从字符串数组中搜索单词。

array = ["ram","gopal","varma","govind","ravan","alan"]

如果我的搜索文本是goal我想列出如下：

result = ["gopal","govind","alan"]

即 gopal 和 goal 中只有 p 缺失，因此它应该在具有更高优先级的搜索列表中。

有什么办法可以做这样的过滤吗？

Answer 1

您想找到最长的公共子序列。我建议您查看 Ray Wenderlich 的 Swift 算法俱乐部上的 this 优秀文章，您可以在其中找到包含示例的解决方案。

编辑：

然后你必须遍历你的数组并跟踪每个世界的子序列有多长（例如在字典中）。然后你必须按子序列长度对你的数组进行排序。

例如像这样：

let array = ["ram", "gopal", "varma", "govind", "ravan", "alan"]
let searchTerm = "goal"

var dictionary: [String: Int] = [:]
for element in array {
    dictionary[element] = searchTerm.longestCommonSubsequence(element).count
}

let result = dictionary.sorted(by: { [=10=].1 > .1 }).map { [=10=].key }

Answer 2

两个字符串之间的最长公共子序列可以递归定义如下：

func lcs(_ str1: String, _ str2: String, _ i: String.Index, _ j: String.Index) -> Int 
{
    if (i == str1.startIndex || j == str2.startIndex) {
        return 0
    }

    let beforeI = str1.index(before: i)
    let beforeJ = str2.index(before: j)

    if str1[beforeI] == str2[beforeJ] {
        return 1 + lcs(str1, str2, beforeI, beforeJ)
    } else {
        return max(lcs(str1, str2, i, beforeJ), lcs(str1, str2, beforeI, j))
    }
}

您可以找到有关此动态规划算法如何工作的完整解释 here。

因此，给定一个字符串数组和一个搜索文本：

let array = ["ram", "gopal", "varma", "govind", "ravan", "alan", "logan"]
let searchText = "goal"

我们可以为数组的每个元素关联一个分数，仅过滤那些具有非零分数的元素，按分数对它们进行排序，然后仅键入元组中的单词：

let result = array
    .map { ([=12=], lcs(searchText,
                    [=12=],
                    searchText.endIndex,
                    [=12=].endIndex)) }
    .filter { [=12=].1 > 0 }
    .sorted { [=12=].1 > .1 }
    .map { [=12=].0 }

print(result)

产生：

["gopal", "govind", "alan", "logan", "ram", "varma", "ravan"]

从字符串数组中找到最常见的子字符串

Find most common substring from an Array of Strings

arrays

search

ios

longest-substring

swift