Задача: 524. Longest Word in Dictionary through Deleting
Сложность: medium

Даны строка s и массив строк dictionary. Верните самую длинную строку из dictionary, которую можно сформировать, удаляя некоторые символы из данной строки s. Если возможных результатов несколько, верните самое длинное слово с наименьшим лексикографическим порядком. Если возможного результата нет, верните пустую строку.

Пример:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

👨‍💻 Алгоритм:

1⃣Инициализируйте переменную для хранения самой длинной строки, соответствующей критериям. Пройдите по каждой строке x в неотсортированном массиве dictionary и проверьте, является ли x подпоследовательностью строки s.

2⃣Если строка x является подпоследовательностью, сравните её с текущей самой длинной строкой по длине. Если длина x больше или равна длине текущей самой длинной строки и она меньше текущей строки в лексикографическом порядке (если равны по длине), обновите текущую самую длинную строку.

3⃣После рассмотрения всех строк в dictionary, верните найденную строку. Если ни одна строка не подошла, верните пустую строку.

😎 Решение:

class Solution {
    func isSubsequence(_ x: String, _ y: String) -> Bool {
        var j = x.startIndex
        for i in y.indices where j < x.endIndex {
            if x[j] == y[i] {
                j = x.index(after: j)
            }
        }
        return j == x.endIndex
    }

    func findLongestWord(_ s: String, _ d: [String]) -> String {
        var maxStr = ""
        for str in d {
            if isSubsequence(str, s) {
                if str.count > maxStr.count || (str.count == maxStr.count && str < maxStr) {
                    maxStr = str
                }
            }
        }
        return maxStr
    }
}

Ставь 👍 и забирай 📚 Базу знаний