Найти наиболее распространенную подстроку из массива строк - PullRequest
Новая
       16

Найти наиболее распространенную подстроку из массива строк

0 голосов
/ 22 февраля 2019

Я хочу найти слово из массива строк. 

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

, если мой текст для поиска goal, я хочу перечислить следующее: 

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

т.е. вgopal & goal only p отсутствует, поэтому он должен быть в списке поиска с более высоким приоритетом.

Есть ли способ выполнить такую ​​фильтрацию?

Ответы [ 2 ]

0 голосов
/ 23 февраля 2019

Самая длинная общая подпоследовательность между двумя строками может быть рекурсивно определена следующим образом: 

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))
    }
}

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

Итак, учитывая массив строк и текст для поиска: 

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

Мы можем связать оценку с каждым элементом массива, отфильтровать только те, которые имеют ненулевую оценку, отсортировать их понабрать, а затем набрать только слова из кортежей: 

let result = array
    .map { ($0, lcs(searchText,
                    $0,
                    searchText.endIndex,
                    $0.endIndex)) }
    .filter { $0.1 > 0 }
    .sorted { $0.1 > $1.1 }
    .map { $0.0 }

print(result)

Что дает:

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

0 голосов
/ 22 февраля 2019

Вы хотите найти самые длинные общие подпоследовательности.Я бы посоветовал вам взглянуть на эту отличную статью о Swift Algorithm Club Рэя Вендерлиха, где вы можете найти свое решение с примерами.над вашим массивом и отслеживайте, как долго подпоследовательность для каждого мира (например, в словаре).Затем вы должны отсортировать ваш массив по длине подпоследовательностей.

Например, вот так: 

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: { $0.1 > $1.1 }).map { $0.key }
...