648. Replace Words

LeetCode medium original: C# #csharp #hash-table #leetcode #medium #prefix-sum #search #string #tree

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

В английском языке есть понятие "корень", за которым может следовать какое-то другое слово, чтобы образовать другое более длинное слово - назовем это слово производным. НаExemple, если за корнем "help" следует слово "ful", мы можем образовать производное "helpful". Дайте словарь, состоящий из множества корней, и предложение, состоящее из слов, разделенных пробелами, замените все производные в предложении на образующий их корень. Если производное может быть заменено более чем одним корнем, замените его корнем, имеющим наименьшую длину. return предложение после замены.

Exemple:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"

Output: "the cat was rat by the bat"

C# solution

correspondant/original

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public string ReplaceWords(IList<string> roots, string sentence) {
        var rootSet = new HashSet<string>(roots);
        
        string Replace(string word) {
            for (int i = 1; i <= word.Length; i++) {
                string prefix = word.Substring(0, i);
                if (rootSet.Contains(prefix)) {
                    return prefix;
                }
            }
            return word;
        }
        
        return string.Join(" ", sentence.Split(new char[] { ' ' }).Select(Replace));
    }
}

C++ solution

brouillon automatique, à relire avant soumission

#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 ReplaceWords(vector<string> roots, string sentence) {
        var rootSet = new HashSet<string>(roots);
        
        string Replace(string word) {
            for (int i = 1; i <= word.size(); i++) {
                string prefix = word.Substring(0, i);
                if (rootSet.Contains(prefix)) {
                    return prefix;
                }
            }
            return word;
        }
        
        return string.Join(" ", sentence.Split(new char[] { ' ' }).Select(Replace));
    }
}

Java solution

correspondant/original

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
    public String replaceWords(List<String> roots, String sentence) {
        Set<String> rootSet = new HashSet<>(roots);
        
        StringBuilder result = new StringBuilder();
        for (String word : sentence.split(" ")) {
            String replacement = word;
            for (int i = 1; i <= word.length(); i++) {
                String prefix = word.substring(0, i);
                if (rootSet.contains(prefix)) {
                    replacement = prefix;
                    break;
                }
            }
            if (result.length() > 0) {
                result.append(" ");
            }
            result.append(replacement);
        }
        
        return result.toString();
    }
}

JavaScript solution

correspondant/original

var replaceWords = function(roots, sentence) {
    const rootSet = new Set(roots);
    
    const replace = (word) => {
        for (let i = 1; i <= word.length; i++) {
            if (rootSet.has(word.slice(0, i))) {
                return word.slice(0, i);
            }
        }
        return word;
    };
    
    return sentence.split(' ').map(replace).join(' ');
};

Python solution

correspondant/original

def replaceWords(roots, sentence):
    root_set = set(roots)
    
    def replace(word):
        for i in range(1, len(word) + 1):
            if word[:i] in root_set:
                return word[:i]
        return word
    
    return ' '.join(map(replace, sentence.split()))

Go solution

correspondant/original

package main

import (
    "fmt"
    "strings"
)

func replaceWords(roots []string, sentence string) string {
    rootSet := make(map[string]struct{})
    for _, root := range roots {
        rootSet[root] = struct{}{}
    }
    
    replace := func(word string) string {
        for i := 1; i <= len(word); i++ {
            if _, exists := rootSet[word[:i]]; exists {
                return word[:i]
            }
        }
        return word
    }
    
    words := strings.Split(sentence, " ")
    for i, word := range words {
        words[i] = replace(word)
    }
    
    return strings.Join(words, " ")
}

Algorithm

Преобразуйте словарь корней в набор для быстрого поиска.

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

Замените слово найденным корнем и соберите обновленное предложение.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.