LeetCode 솔루션 분류
[6/20] 820. Short Encoding of Words
본문
Medium
733275Add to ListShareA valid encoding of an array of words is any reference string s and array of indices indices such that:
words.length == indices.length- The reference string
sends with the'#'character. - For each index
indices[i], the substring ofsstarting fromindices[i]and up to (but not including) the next'#'character is equal towords[i].
Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.
Example 1:
Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"
Example 2:
Input: words = ["t"] Output: 2 Explanation: A valid encoding would be s = "t#" and indices = [0].
Constraints:
1 <= words.length <= 20001 <= words[i].length <= 7words[i]consists of only lowercase letters.
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 394 ms, faster than 26.61% of Python3 online submissions for Short Encoding of Words.
Memory Usage: 17.4 MB, less than 27.98% of Python3 online submissions for Short Encoding of Words.
Memory Usage: 17.4 MB, less than 27.98% of Python3 online submissions for Short Encoding of Words.
class TrieNode:
def __init__(self):
self.children = {}
class Solution:
def minimumLengthEncoding(self, words: List[str]) -> int:
words = list(set(words))
words = sorted(words, reverse=True, key=len)
trie_root = TrieNode()
ends = []
for word in words:
node = trie_root
for char in word[::-1]:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
if not node.children: ends.append(len(word)+1)
return sum(ends)
