[LeetCode] 820 | Short Encoding of Words | Python

---

문제 링크: https://leetcode.com/problems/short-encoding-of-words/

---

문제

A 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.

---

조건

• 1 <= words.length <= 2000
• 1 <= words[i].length <= 7
• words[i] consists of only lowercase letters.

---

내 풀이

words안의 word를 긴 순서대로 정렬한다.

만약 'time', 'me'처럼 substring이 있다면, 이미 ans안에 'time#'이 포함될 것이므로 중복되지 않게 처리할 수 있다.

---

코드

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        words.sort(key=len, reverse=True)
        ans = ''
        
        for word in words:
            if word+'#' not in ans:
                ans += word+'#'
        
        return len(ans)