题目如下:
解题思路:本题考查就是找出一个单词是不是另外一个单词的后缀,如果是的话,就可以Short Encode。所以,我们可以把words中每个单词倒置后排序,然后遍历数组,每个元素只要和其后面相邻的元素比较,如果是后缀则被Short Encode,否则不行。
代码如下:
class Solution(object):
def minimumLengthEncoding(self, words):
"""
:type words: List[str]
:rtype: int
"""
words2 = sorted([i[::-1] for i in words])
res = 0
for i in range(len(words2)-1):
if words2[i+1].find(words2[i]) == 0:
continue
else:
res += len(words2[i]) + 1
res += len(words2[-1]) + 1
return res