2022-02-11：单词缩写。给定一个由n个不重复非空字符串组

原创

福大大架构师每日一题

发布于 2022-02-11 22:18:37

4190

发布于 2022-02-11 22:18:37

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-02-11：单词缩写。

给定一个由n个不重复非空字符串组成的数组，你需要按照以下规则为每个单词生成最小的缩写。

初始缩写由起始字母+省略字母的数量+结尾字母组成。

若存在冲突，亦即多于一个单词有同样的缩写，则使用更长的前缀代替首字母，直到从单词到缩写的映射唯一。换而言之，最终的缩写必须只能映射到一个单词。

若缩写并不比原单词更短，则保留原样。

示例:

输入: "like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"

输出: "l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"

注意:

n和每个单词的长度均不超过 400。

每个单词的长度大于 1。

单词只由英文小写字母组成。

返回的答案需要和原数组保持同一顺序。

力扣527。

答案2022-02-11：

key存缩写词，value存单词列表。

代码用golang编写。代码如下：

package main

import (
    "fmt"
)

func main() {
    words := []string{"like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"}
    ret := wordsAbbreviation(words)
    fmt.Println(ret)
}

func wordsAbbreviation(words []string) []string {
    len0 := len(words)
    res := make([]string, 0)
    map0 := make(map[string][]int)
    for i := 0; i < len0; i++ {
        res = append(res, makeAbbr(words[i], 1))
        list0 := map0[res[i]]
        list0 = append(list0, i)
        map0[res[i]] = list0
    }
    prefix := make([]int, len0)
    for i := 0; i < len0; i++ {
        if len(map0[res[i]]) > 1 {
            indexes := map0[res[i]]
            delete(map0, res[i])
            for _, j := range indexes {
                prefix[j]++
                res[j] = makeAbbr(words[j], prefix[j])
                list0 := map0[res[j]]
                list0 = append(list0, j)
                map0[res[i]] = list0
            }
            i--
        }
    }
    return res
}

func makeAbbr(s string, k int) string {
    if k >= len(s)-2 {
        return s
    }
    builder := make([]byte, 0)
    builder = append(builder, s[0:k]...)
    builder = append(builder, fmt.Sprintf("%d", len(s)-1-k)...)
    builder = append(builder, s[len(s)-1])
    return string(builder)
}

执行结果如下：

左神java代码

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法

登录后参与评论

0 条评论

热度