力扣820.单词的压缩编码
-
反转 + 排序
- 将字符串反转
- 按照字典序排序
- 如果是t和s是后缀关系,那么排序后s一定跟在t后面
- 判断前后项是否有关系
- 如果有 直接跳过
-
class Solution {public:int minimumLengthEncoding(vector<string>& words) {int n = words.size();vector<string> reversed_words;for(string word:words){reverse(word.begin(),word.end());reversed_words.emplace_back(word);}sort(reversed_words.begin(),reversed_words.end());int res=0;for(int i=0;i<n;i++){//有关系的直接跳过if(i < n - 1 && reversed_words[i+1].find(reversed_words[i]) == 0){}else res += reversed_words[i].size() + 1;}return res;}};