엔지니어 게시판
LeetCode 솔루션 분류

# [6/20] 820. Short Encoding of Words

• mingki 작성
• 작성일

• 60 조회
• 1 댓글

### 본문

Medium

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 `s` ends with the `'#'` character.
• For each index `indices[i]`, the substring of `s` starting from `indices[i]` and up to (but not including) the next `'#'` character is equal to `words[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 <= 2000`
• `1 <= words[i].length <= 7`
• `words[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.
``````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)
``````
전체 126 / 1 페이지

• 등록일 13:55
• 등록일 13:17
• 등록일 11:20
• 등록일 06.23
• 등록일 06.23
• 등록일 06.23
• 등록일 06.23
• 등록일 06.23
• 등록일 06.23

### 새댓글

• 등록자 학부유학생 등록일 06.22
• 등록자 학부유학생 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 SVKOREANS 등록일 06.20
• 등록자 학부유학생 등록일 06.20
• 등록자 Coffee 등록일 06.20
• 등록자 키위 등록일 06.20
• 등록자 학부유학생 등록일 06.19
• 등록자 학부유학생 등록일 06.19

### Stats

• 현재 접속자 83 명
• 오늘 방문자 614 명
• 어제 방문자 683 명
• 최대 방문자 1,262 명
• 전체 회원수 264 명