411. Minimum Unique Word Abbreviation

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public string MinAbbreviation(string target, string[] dictionary) {
        var targetAbbrs = GenerateAbbreviations(target);
        var dictAbbrs = new HashSet<string>();
        foreach (var word in dictionary) {
            dictAbbrs.UnionWith(GenerateAbbreviations(word));
        }
        targetAbbrs.ExceptWith(dictAbbrs);
        return targetAbbrs.OrderBy(abbr => abbr.Length).FirstOrDefault();
    }
    private HashSet<string> GenerateAbbreviations(string word) {
        var result = new HashSet<string>();
        GenerateAbbreviationsHelper(word.ToCharArray(), "", 0, 0, result);
        return result;
    }
    private void GenerateAbbreviationsHelper(char[] word, string current, int pos, int count, HashSet<string> result) {
        if (pos == word.Length) {
            result.Add(current + (count > 0 ? count.ToString() : ""));
            return;
        }
        GenerateAbbreviationsHelper(word, current, pos + 1, count + 1, result);
        GenerateAbbreviationsHelper(word, current + (count > 0 ? count.ToString() : "") + word[pos], pos + 1, 0, result);
    }
}

#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 MinAbbreviation(string target, vector<string> dictionary) {
        var targetAbbrs = GenerateAbbreviations(target);
        var dictAbbrs = new HashSet<string>();
        foreach (var word in dictionary) {
            dictAbbrs.UnionWith(GenerateAbbreviations(word));
        }
        targetAbbrs.ExceptWith(dictAbbrs);
        return targetAbbrs.OrderBy(abbr => abbr.size()).FirstOrDefault();
    }
    private HashSet<string> GenerateAbbreviations(string word) {
        var result = new HashSet<string>();
        GenerateAbbreviationsHelper(word.ToCharArray(), "", 0, 0, result);
        return result;
    }
    private void GenerateAbbreviationsHelper(char[] word, string current, int pos, int count, HashSet<string> result) {
        if (pos == word.size()) {
            result.push_back(current + (count > 0 ? count.ToString() : ""));
            return;
        }
        GenerateAbbreviationsHelper(word, current, pos + 1, count + 1, result);
        GenerateAbbreviationsHelper(word, current + (count > 0 ? count.ToString() : "") + word[pos], pos + 1, 0, result);
    }
}

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

public class Solution {
    public String minAbbreviation(String target, String[] dictionary) {
        Set<String> targetAbbrs = generateAbbreviations(target);
        Set<String> dictAbbrs = new HashSet<>();
        for (String word : dictionary) {
            dictAbbrs.addAll(generateAbbreviations(word));
        }
        targetAbbrs.removeAll(dictAbbrs);
        return targetAbbrs.stream().min((a, b) -> Integer.compare(a.length(), b.length())).orElse("");
    }

    private Set<String> generateAbbreviations(String word) {
        Set<String> result = new HashSet<>();
        generateAbbreviationsHelper(word.toCharArray(), "", 0, 0, result);
        return result;
    }

    private void generateAbbreviationsHelper(char[] word, String current, int pos, int count, Set<String> result) {
        if (pos == word.length) {
            result.add(current + (count > 0 ? count : ""));
            return;
        }
        generateAbbreviationsHelper(word, current, pos + 1, count + 1, result);
        generateAbbreviationsHelper(word, current + (count > 0 ? count : "") + word[pos], pos + 1, 0, result);
    }
}

function generateAbbreviations(word) {
    function helper(word, current, pos, count, result) {
        if (pos === word.length) {
            result.add(current + (count > 0 ? count : ""));
            return;
        }
        helper(word, current, pos + 1, count + 1, result);
        helper(word, current + (count > 0 ? count : "") + word[pos], pos + 1, 0, result);
    }

    const result = new Set();
    helper(word, "", 0, 0, result);
    return result;
}

function minAbbreviation(target, dictionary) {
    const targetAbbrs = generateAbbreviations(target);
    const dictAbbrs = new Set();
    for (const word of dictionary) {
        for (const abbr of generateAbbreviations(word)) {
            dictAbbrs.add(abbr);
        }
    }
    const validAbbrs = new Set([...targetAbbrs].filter(x => !dictAbbrs.has(x)));
    return [...validAbbrs].reduce((a, b) => a.length <= b.length ? a : b);
}

def generate_abbreviations(word):
    def helper(word, current, pos, count, result):
        if pos == len(word):
            result.add(current + (str(count) if count > 0 else ""))
            return
        helper(word, current, pos + 1, count + 1, result)
        helper(word, current + (str(count) if count > 0 else "") + word[pos], pos + 1, 0, result)
    
    result = set()
    helper(word, "", 0, 0, result)
    return result

def min_abbreviation(target, dictionary):
    target_abbrs = generate_abbreviations(target)
    dict_abbrs = set()
    for word in dictionary:
        dict_abbrs.update(generate_abbreviations(word))
    valid_abbrs = target_abbrs - dict_abbrs
    return min(valid_abbrs, key=len)

package main

import (
    "sort"
    "strconv"
)

func generateAbbreviations(word string) map[string]struct{} {
    result := make(map[string]struct{})
    helper(word, "", 0, 0, result)
    return result
}

func helper(word, current string, pos, count int, result map[string]struct{}) {
    if pos == len(word) {
        if count > 0 {
            current += strconv.Itoa(count)
        }
        result[current] = struct{}{}
        return
    }
    helper(word, current, pos+1, count+1, result)
    if count > 0 {
        current += strconv.Itoa(count)
    }
    helper(word, current+string(word[pos]), pos+1, 0, result)
}

func minAbbreviation(target string, dictionary []string) string {
    targetAbbrs := generateAbbreviations(target)
    dictAbbrs := make(map[string]struct{})
    for _, word := range dictionary {
        for abbr := range generateAbbreviations(word) {
            dictAbbrs[abbr] = struct{}{}
        }
    }
    validAbbrs := make([]string, 0)
    for abbr := range targetAbbrs {
        if _, exists := dictAbbrs[abbr]; !exists {
            validAbbrs = append(validAbbrs, abbr)
        }
    }
    sort.Slice(validAbbrs, func(i, j int) bool {
        return len(validAbbrs[i]) < len(validAbbrs[j])
    })
    return validAbbrs[0]
}

// Пример использования
func main() {
    target := "substitution"
    dictionary := []string{"substitution", "subtitution", "substitutio"}
    println(minAbbreviation(target, dictionary))
}

Explanation

Algorithm

Создайте множество всех аббревиатур из словаря, вычислив их все возможные аббревиатуры.

Сгенерируйте все возможные аббревиатуры для строки target.

Найдите самую короткую аббревиатуру для target, которая отсутствует в множестве аббревиатур словаря.

😎