golang 解法, 执行用时: 32 ms, 内存消耗: 6.7 MB, 提交时间: 2023-10-22 10:52:39

import "fmt"

func abbr(s string, k int) string {
	if k >= len(s)-2 {
		return s
	}
	return fmt.Sprintf("%s%d%c", s[:k], len(s)-k-1, s[len(s)-1])
}

func wordsAbbreviation(dict []string) []string {
	n := len(dict)
	pre := make([]int, n)
	out := make([]string, n)
	for i := 0; i < n; i++ {
		pre[i], out[i] = 1, abbr(dict[i], 1)
	}
	for i := 0; i < n; i++ {
		for {
			s := map[int]bool{}
			for j := i + 1; j < n; j++ {
				if out[j] == out[i] {
					s[j] = true
				}
			}
			if 0 == len(s) {
				break
			}
			s[i] = true
			for k, _ := range s {
				pre[k]++
				out[k] = abbr(dict[k], pre[k])
			}
		}
	}
	return out
}

java 解法, 执行用时: 27 ms, 内存消耗: 55.8 MB, 提交时间: 2023-10-22 10:52:14

class Solution {
    public List<String> wordsAbbreviation(List<String> words) {
        // 典型的分组加上字典树的操作套路
        // 1.对于前后缀的字符进行hash操作，然后做一个横向的扩展
        // value对应的是前后字母相同的字符串在words中的索引位置
        Map<String, List<Integer>> modeGroup = new HashMap<>();
        for (int i = 0; i < words.size(); i++) {
            // 这样处理之后得到的同一个分组的字符串长度都是相同的
            String key = getAbb(words, i, 0);
            List<Integer> tmp = modeGroup.getOrDefault(key, new ArrayList<>());
            tmp.add(i);
            modeGroup.put(key, tmp);
        }

        // 2.开始进行每个分组下的字典树构建和缩写操作
        int n = words.size();
        String[] strs = new String[n];
        for (List<Integer> mode : modeGroup.values()) {
            // 做了一个special-case的处理
            if (mode.size() <= 1) {
                String abb = getAbb(words, mode.get(0), 0);
                strs[mode.get(0)] = abb;
            } else {
                TrieNode root = new TrieNode();
                for (int index : mode) {
                    TrieNode cur = root;
                    // tips:这个地方是考虑到了当长度为2的时候如何进行处理，因此加入了尾部的字符
                    for (char c : words.get(index).substring(1).toCharArray()) {
                        if (cur.children[c - 'a'] == null) {
                            cur.children[c - 'a'] = new TrieNode();
                        }
                        cur.count++;
                        cur = cur.children[c - 'a'];
                    }
                }

                for (int index : mode) {
                    TrieNode cur = root;
                    int preFix = 0;
                    for (char c : words.get(index).substring(1).toCharArray()) {
                        if (cur.count == 1) {
                            break;
                        } else {
                            cur = cur.children[c - 'a'];
                            preFix++;
                        }
                    }
                    String abb = getAbb(words, index, preFix);
                    strs[index] = abb;
                }
            }
        }

        // 按照字符串的顺序做整体的整理操作
        List<String> ans = new ArrayList<>();
        for (String str : strs) {
            ans.add(str);
        }

        return ans;
    }

    private String getAbb(List<String> words, int index, int preFix) {
        String word = words.get(index);
        int len = word.length();
        if (len - preFix <= 3) return word;
        return word.substring(0, preFix + 1) + (len - preFix - 2) + word.charAt(len - 1);
    }

    class TrieNode {
        TrieNode[] children;
        int count;

        TrieNode() {
            children = new TrieNode[26];
            count = 0;
        }
    }
}

python3 解法, 执行用时: 64 ms, 内存消耗: 17.3 MB, 提交时间: 2023-10-22 10:51:51

class Solution:
    def wordsAbbreviation(self, lst: List[str]) -> List[str]:
        from collections import defaultdict

        def abbr(word, target_len=3):
            # 用来生成缩略词的函数，target_len是最终的缩略词长度
            if len(word) <= target_len:
                return word
            else:
                return word[0:target_len - 2] + str(len(word) - target_len + 1) + word[-1]

        def recur(words, target_len=3):
            # 返回满足条件的单词-缩略词字典映射，以及不唯一的单词作为remaining，后续需要继续处理
            abbr_dict = defaultdict(list)
            for word in words:
                abbr_dict[abbr(word, target_len)].append(word)

            res = {}
            remaining = []
            for key, values in abbr_dict.items():
                if len(abbr_dict[key]) == 1: # 结果唯一，记录单词形如: {'like': 'l2e'}
                    res[values[0]] = key
                else:
                    remaining.extend(values) # 缩略词不唯一的单词将被收录到remaining中
            return res, remaining

        words = lst
        res = {}
        target_len = 3
        while words:
            tmp_res, words = recur(words, target_len)  # 缩略词不唯一的单词，重新做为word，进行下一次循环
            res.update(tmp_res) # 更新结果字典
            target_len += 1

        res_list = [res[word] for word in lst] # 按顺序输出缩略词

        return res_list