LeetCode 820. 单词的压缩编码

Categories:

题目描述
思路分析
1. 解法一：删除后缀（推荐）
相似题目

题目描述

✅ 820. 单词的压缩编码

思路分析

解法一：删除后缀（推荐）

核心思路：

用集合保存所有单词。

对每个单词删除其所有非空后缀。

剩余单词集合中的单词就是编码需要保留的单词。

结果为 sum(len(word) + 1)。

复杂度分析：

时间复杂度：O(sumLen^2)，sumLen 为总字符数。

空间复杂度：O(sumLen)。

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Set<String> set = new HashSet<>();
        for (String w : words) {
            set.add(w);
        }

        for (String w : words) {
            for (int i = 1; i < w.length(); i++) {
                set.remove(w.substring(i));
            }
        }

        int ans = 0;
        for (String w : set) {
            ans += w.length() + 1;
        }
        return ans;
    }
}

func minimumLengthEncoding(words []string) int {
	set := make(map[string]bool)
	for _, w := range words {
		set[w] = true
	}

	for _, w := range words {
		for i := 1; i < len(w); i++ {
			delete(set, w[i:])
		}
	}

	ans := 0
	for w := range set {
		ans += len(w) + 1
	}
	return ans
}

相似题目

题目	难度	考察点
820. 单词的压缩编码	中等	Trie/集合
648. 单词替换	中等	Trie
208. 实现 Trie (前缀树)	中等	Trie
211. 添加与搜索单词 - 数据结构设计	中等	Trie
472. 连接词	困难	Trie
1268. 搜索推荐系统	中等	Trie

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/19275870