720. Longest Word in Dictionary

LeetCode medium original: C# #array #csharp #graph #hash-table #leetcode #medium #prefix-sum #sort #string #tree

El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.

LeetCode Static

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

Ejemplo:

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

Output: "world"

C# solución

coincidente/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++ solución

borrador automático, revisar antes de enviar

#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 solución

coincidente/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 solución

coincidente/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 solución

coincidente/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 solución

coincidente/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
}

Algorithm

Отсортируйте arreglo слов по длине и лексикоgrafoическому порядку.

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

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

😎

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes

Todavía no hay vacantes activas.