720. Longest Word in Dictionary

LeetCode medium оригинал: C# #array #csharp #graph #hash-table #leetcode #medium #prefix-sum #sort #string #tree

LeetCode Static

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

Пример:

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

Output: "world"

C# решение

сопоставлено/оригинал

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++ решение

auto-draft, проверить перед отправкой

#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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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
}

Algorithm

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

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

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

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.