Решение: самое длинное слово в словаре через удаление

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашел его полезным, Пожалуйста, как Этот пост и/или УПОТАТЬ Мое решение пост на форумах LeetCode Отказ

Проблема летакода # 524 (Средний): самое длинное слово в словаре через удаление

Описание:

( Перейти к : Идея решения Код : JavaScript | Python |. Java |. C ++

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

Примеры:

Ограничения:

• Все строки на входе будут содержать только строчные буквы.
• Размер словаря не превышает 1000 Отказ
• Длина всех строк на входе не превышает 1000 Отказ

Идея:

( Перейти к : Описание проблемы Код : JavaScript | Python |. Java |. C ++

Чтобы избежать необходимости отсортировать словарь ( d ), мы можем просто отслеживать наш лучший ответ ( ans ) и пропустить любые слова, которые были бы хуже ответа, чем текущий.

Тогда мы можем просто проверить каждый слово Чтобы увидеть, сможем ли мы найти Чар Внутри S для того, чтобы слово Отказ Мы можем использовать функцию индексации строки для хорошего эффекта здесь, чтобы начать каждый новый Чар поиск сразу после позиции ( POS ) последнего Чар нашел.

Если мы не сможем найти Чар , Перерыв к следующему слово Отказ Если мы успешно достигнем конца слово мы можем вернуть Это. Если мы никогда не найдем действительны слово Матч, вернуть пустая строка.

Выполнение:

Код для всех четырех языков практически идентичен.

Java не позволит вам напрямую сравнивать две строки с большей/меньше, чем, поэтому мы можем использовать .по сравнению с () .

Код JavaScript:

( Перейти к : Описание проблемы Идея решения

var findLongestWord = function(S, D) {
    let ans = ""
    for (let word of D) {
        let a = word.length, b = ans.length
        if (a < b || (a === b && word > ans)) continue
        let pos = -1
        for (let char of word) {
            pos = S.indexOf(char, pos + 1)
            if (pos === -1) break
        }
        if (pos !== -1) ans = word
    }
    return ans
};

Код Python:

( Перейти к : Описание проблемы Идея решения

class Solution:
    def findLongestWord(self, S: str, D: List[str]) -> str:
        ans = ""
        for word in D:
            a, b = len(word), len(ans)
            if a < b or (a == b and word > ans): continue
            pos = -1
            for char in word:
                pos = S.find(char, pos + 1)
                if pos == -1: break
            if pos != -1: ans = word
        return ans

Java код:

( Перейти к : Описание проблемы Идея решения

class Solution {
    public String findLongestWord(String S, List D) {
        String ans = "";
        for (String word : D) {
            int a = word.length(), b = ans.length();
            if (a < b || (a == b && word.compareTo(ans) > 0)) continue;
            int pos = -1;
            for (int i = 0; i < a; i++) {
                pos = S.indexOf(word.charAt(i), pos + 1);
                if (pos == -1) break;
            }
            if (pos != -1) ans = word;
        }
        return ans;
    }
}

C ++ код:

( Перейти к : Описание проблемы Идея решения

class Solution {
public:
    string findLongestWord(string S, vector& D) {
        string ans = "";
        for (string word : D) {
            int a = word.length(), b = ans.length();
            if (a < b || (a == b && word > ans)) continue;
            int pos = -1;
            for (int i = 0; i < a; i++) {
                pos = S.find(word[i], pos + 1);
                if (pos == -1) break;
            }
            if (pos != -1) ans = word;
        }
        return ans;
    }
};

Оригинал: “https://dev.to/seanpgallivan/solution-longest-word-in-dictionary-through-deleting-pd8”