leetcode - 527. Word Abbreviation-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode - 527. Word Abbreviation。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Description

Given an array of distinct strings words, return the minimal possible abbreviations for every word.

The following are the rules for a string abbreviation:

The initial abbreviation for each word is: the first character, then the number of characters in between, followed by the last character.
If more than one word shares the same abbreviation, then perform the following operation:
- Increase the prefix (characters in the first part) of each of their abbreviations by 1.
  - For example, say you start with the words [“abcdef”,“abndef”] both initially abbreviated as “a4f”. Then, a sequence of operations would be [“a4f”,“a4f”] -> [“ab3f”,“ab3f”] -> [“abc2f”,“abn2f”].
- This operation is repeated until every abbreviation is unique.
At the end, if an abbreviation did not make a word shorter, then keep it as the original word.

Example 1:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

Example 2:

Input: words = ["aa","aaa"]
Output: ["aa","aaa"]

Constraints:

1 <= words.length <= 400
2 <= words[i].length <= 400
words[i] consists of lowercase English letters.
All the strings of words are unique.

Solution

Just code intuitively… Write a function for doing the abbreviation, and then use a dict, with the key as the abbreviation, and value as the list of common words indexes. Every time add the list with length 1, and keep expanding those list with length more than 1.文章来源地址https://www.toymoban.com/news/detail-820516.html

Code

class Solution:
    def wordsAbbreviation(self, words: List[str]) -> List[str]:
        def abbrev(s: str, prefix_len: int) -> str:
            abbr = f'{s[:prefix_len]}{len(s) - prefix_len - 1}{s[-1]}'
            if len(abbr) >= len(s):
                abbr = s
            return abbr
        # key: abbr, value: [index1, index2, ...]}
        abbr_info = {}
        cur_prefix = 1
        # init abbr_info
        for i in range(len(words)):
            abbr = abbrev(words[i], cur_prefix)
            if abbr not in abbr_info:
                abbr_info[abbr] = []
            abbr_info[abbr].append((i, abbr))
        res = []
        while abbr_info:
            new_abbr_info = {}
            cur_prefix += 1
            for each_abbr, same_list in abbr_info.items():
                if len(same_list) == 1:
                    res.append(same_list[0])
                else:
                    for index, _ in same_list:
                        new_abbr = abbrev(words[index], cur_prefix)
                        if new_abbr not in new_abbr_info:
                            new_abbr_info[new_abbr] = []
                        new_abbr_info[new_abbr].append((index, new_abbr))
            abbr_info = new_abbr_info
        res.sort(key=lambda x:x[0])
        return list(item[1] for item in res)