527 - Word Abbreviation
Details
Key | Value |
---|---|
Link | https://leetcode.com/problems/word-abbreviation/ |
Language | Python 3 |
Runtime | 787 ms, faster than 27.16% of Python3 online submissions for Word Abbreviation |
Memory Usage | 65.2 MB, less than 14.57% of Python3 online submissions for Word Abbreviation |
Datastructures | List[str] |
Algorithms | Group + Least Common Prefix? |
Complexity | Time: O(ClogC) Memory: O(C) (C=number of characters in all words in array) |
Procedure
- ...
Code
class Solution:
def wordsAbbreviation(self, words: List[str]) -> List[str]:
groups = collections.defaultdict(int)
for i, word in enumerate(words):
for j in range(1, len(word) - 2):
groups[ word[:j] + str( len(word)-j-1 ) + word[-1] ] += 1
for i, word in enumerate(words):
for j in range(1, len(word) - 2):
new_group = word[:j] + str(len(word)-j-1) + word[-1]
if groups[new_group] == 1:
words[i] = new_group
break
return words