720. Longest Word in Dictionary

leetcode medium

#array#csharp#graph#hash-table#leetcode#medium#prefix-sum#sort#string#tree

Task

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

Пример:

Input: words = ["w","wo","wor","worl","world"]

Output: "world"

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public string LongestWord(string[] words) {
        Array.Sort(words);
        HashSet<string> validWords = new HashSet<string>();
        validWords.Add("");
        string longest = "";
        foreach (string word in words) {
            if (validWords.Contains(word.Substring(0, word.Length - 1))) {
                validWords.Add(word);
                if (word.Length > longest.Length) {
                    longest = word;
                }
            }
        }
        return longest;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string LongestWord(vector<string> words) {
        sort(words.begin(), words.end());
        HashSet<string> validWords = new HashSet<string>();
        validWords.push_back("");
        string longest = "";
        foreach (string word in words) {
            if (validWords.Contains(word.Substring(0, word.size() - 1))) {
                validWords.push_back(word);
                if (word.size() > longest.size()) {
                    longest = word;
                }
            }
        }
        return longest;
    }
}

Java solution

matched/original

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> validWords = new HashSet<>();
        validWords.add("");
        String longest = "";
        for (String word : words) {
            if (validWords.contains(word.substring(0, word.length() - 1))) {
                validWords.add(word);
                if (word.length() > longest.length()) {
                    longest = word;
                }
            }
        }
        return longest;
    }
}

JavaScript solution

matched/original

var longestWord = function(words) {
    words.sort();
    let validWords = new Set([""]);
    let longest = "";
    for (let word of words) {
        if (validWords.has(word.slice(0, -1))) {
            validWords.add(word);
            if (word.length > longest.length) {
                longest = word;
            }
        }
    }
    return longest;
};

Python solution

matched/original

def longestWord(words):
    words.sort()
    valid_words = {""}
    longest = ""
    for word in words:
        if word[:-1] in valid_words:
            valid_words.add(word)
            if len(word) > len(longest):
                longest = word
    return longest

Go solution

matched/original

package main

import (
    "sort"
)

func longestWord(words []string) string {
    sort.Strings(words)
    validWords := map[string]struct{}{ "": {} }
    longest := ""
    for _, word := range words {
        if _, ok := validWords[word[:len(word)-1]]; ok {
            validWords[word] = struct{}{}
            if len(word) > len(longest) {
                longest = word
            }
        }
    }
    return longest
}

Explanation

Algorithm

Отсортируйте массив слов по длине и лексикографическому порядку.

Используйте множество для отслеживания слов, которые можно построить.

Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве.

😎