820. Short Encoding of Words

leetcode

#array#csharp#hash-table#leetcode#string#tree

Task

: medium

Допустимым кодированием массива слов является любая опорная строка s и массив индексов indices, такие что:

words.length == indices.length

Опорная строка s заканчивается символом '#'.

Для каждого индекса indices[i], подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включительно) следующим символом '#', равна words[i].

Дан массив слов, верните длину самой короткой возможной опорной строки s для любого допустимого кодирования слов.

Пример:

Input: words = ["time", "me", "bell"]

Output: 10

Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].

words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"

words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"

words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

C# solution

matched/original

public class Solution {
    public int MinimumLengthEncoding(string[] words) {
        var good = new HashSet<string>(words);
        foreach (var word in words) {
            for (int k = 1; k < word.Length; k++) {
                good.Remove(word.Substring(k));
            }
        }
        int length = 0;
        foreach (var word in good) {
            length += word.Length + 1;
        }
        return length;
    }
}

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 int MinimumLengthEncoding(vector<string> words) {
        var good = new HashSet<string>(words);
        foreach (var word in words) {
            for (int k = 1; k < word.size(); k++) {
                good.Remove(word.Substring(k));
            }
        }
        int length = 0;
        foreach (var word in good) {
            length += word.size() + 1;
        }
        return length;
    }
}

Java solution

matched/original

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Set<String> good = new HashSet<>(Arrays.asList(words));
        for (String word : words) {
            for (int k = 1; k < word.length(); k++) {
                good.remove(word.substring(k));
            }
        }
        int length = 0;
        for (String word : good) {
            length += word.length() + 1;
        }
        return length;
    }

JavaScript solution

matched/original

var minimumLengthEncoding = function(words) {
    let good = new Set(words);
    for (let word of words) {
        for (let k = 1; k < word.length; k++) {
            good.delete(word.substring(k));
        }
    }
    let length = 0;
    for (let word of good) {
        length += word.length + 1;
    }
    return length;

Python solution

matched/original

class Solution:
    def minimumLengthEncoding(self, words):
        good = set(words)
        for word in words:
            for k in range(1, len(word)):
                good.discard(wo

Go solution

matched/original

func minimumLengthEncoding(words []string) int {
    good := make(map[string]struct{})
    for _, word := range words {
        good[word] = struct{}{}
    }
    for _, word := range words {
        for k := 1; k < len(word); k++ {
            delete(good, word[k:])
        }
    }
    length := 0
    for word := range good {
        length += len(word) + 1
    }
    return length
}

Explanation

Algorithm

Поскольку слово имеет не более 6 собственных суффиксов (так как words[i].length <= 7), давайте итерироваться по всем из них. Для каждого собственного суффикса мы попытаемся удалить его из нашего списка слов. Для эффективности сделаем words множеством.

Затем создадим список оставшихся слов и сформируем опорную строку, объединяя каждое слово с символом '#'.

В конце вернем длину полученной опорной строки.

😎