Golang | LeetCode

#hard
Задача: 411. Minimum Unique Word Abbreviation

Строку можно сократить, заменив любое количество не смежных подстрок их длинами. Например, строка "substitution" может быть сокращена как (но не ограничиваясь этим):

"s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("substitution") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замен подстрок) Обратите внимание, что "s55n" ("s ubsti tutio n") не является правильным сокращением "substitution", поскольку замененные подстроки являются смежными.

Длина аббревиатуры - это количество букв, которые не были заменены, плюс количество подстрок, которые были заменены. Например, аббревиатура "s10n" имеет длину 3 (2 буквы + 1 подстрока), а "su3i1u2on" - 9 (6 букв + 3 подстроки). Учитывая целевую строку target и массив строк dictionary, верните аббревиатуру target с наименьшей возможной длиной, которая не является аббревиатурой ни одной строки в словаре. Если существует несколько самых коротких аббревиатур, верните любую из них.

Пример:

Input: target = "apple", dictionary = ["blade"]
Output: "a4"

👨‍💻

Алгоритм:

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

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

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

😎

Решение:

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))
}

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post