Задача: 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 {
    function isSubsequence($x, $y) {
        $j = 0;
        for ($i = 0; $i < strlen($y) && $j < strlen($x); $i++) {
            if ($x[$j] == $y[$i]) {
                $j++;
            }
        }
        return $j == strlen($x);
    }

    function findLongestWord($s, $d) {
        $max_str = "";
        foreach ($d as $str) {
            if ($this->isSubsequence($str, $s)) {
                if (strlen($str) > strlen($max_str) || (strlen($str) == strlen($max_str) && strcmp($str, $max_str) < 0)) {
                    $max_str = $str;
                }
            }
        }
        return $max_str;
    }
}

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