当前位置： 首页 > news >正文

LeetCode 820 单词的压缩编码题解

news 来源：原创 2025/6/28 22:53:39

LeetCode 820 单词的压缩编码题解

题目描述

题目链接
给定一个单词列表，将其编码为一个索引字符串S，格式为"单词1#单词2#…"。要求当某个单词是另一个单词的后缀时，该单词可以被省略。求最终编码字符串的最小长度。

解题思路

逆序前缀树法

  1. 逆序建树：将单词逆序插入前缀树（如"time"→"emit"）
    逆序插入原理 将单词逆序后插入前缀树，使得：
    • me → em 成为 time → emit 的前缀路径
    • 在树结构中， em 路径会被 emit 完全包含
    • 通过检查路径末端是否为叶子节点判断是否需要保留
  2. 统计叶子：只有叶子节点对应的单词需要保留
    • me 的逆序 em 路径末端仍有子节点（继续通向 i ）
    • time 的逆序 emit 路径末端是叶子节点
    • 因此只保留 time 和 bell
  3. 计算长度：每个保留单词的长度+1（#号）
    每个保留单词的贡献长度为：
    原长度 + 1（#号分隔符）
    示例计算： time(4) + 1 + bell(4) + 1 = 10

完整代码实现

from typing import Listclass TrieNode:def __init__(self):self.children = {}  # 存储子节点class Solution:def minimumLengthEncoding(self, words: List[str]) -> int:# 1. 构建逆序前缀树root = TrieNode()# 用字典保存单词最后节点和单词长度nodes = {}for word in set(words):  # 去重处理node = root# 逆序插入字符for c in reversed(word):if c not in node.children:node.children[c] = TrieNode()node = node.children[c]nodes[node] = len(word) + 1  # 存储单词长度+1（#号）# 2. 统计需要保留的单词长度total = 0for node, length in nodes.items():if not node.children:  # 叶子节点（无子节点）total += lengthreturn totalif __name__ == "__main__":# 测试用例test1 = Solution().minimumLengthEncoding(["time", "me", "bell"])  # 10test2 = Solution().minimumLengthEncoding(["t"])  # 2print(test1, test2)

相关文章：

LeetCode 820 单词的压缩编码题解

LeetCode 820 单词的压缩编码题解 题目描述 题目链接 给定一个单词列表，将其编码为一个索引字符串S，格式为"单词1#单词2#…"。要求当某个单词是另一个单词的后缀时，该单词可以被省略。求最终编码字符串的最小长度。 解题思路 逆…...

编程日记 2025/6/28 22:53:39

Windows软件插件-写wav

下载本插件 本插件，将PCM音频流写入WAV音频文件。或将PCM音频流压缩为ALAW格式，写入WAV文件。可以创作大文件（超过4字节所能表示的大小）。插件类型为DLL，可以在win32和MFC程序中使用。使用本插件创建的ALAW格式WAV音频…...

编程日记 2025/6/28 22:53:40

基于 Spring Boot 瑞吉外卖系统开发（十五）

基于 Spring Boot 瑞吉外卖系统开发（十五） 前台用户登录 在登录页面输入验证码，单击“登录”按钮，页面会携带输入的手机号和验证码向“/user/login”发起请求。 定义UserMapper接口 Mapper public interface UserMapper exte…...

编程日记 2025/6/28 23:13:39

【Linux高级IO】多路转接之epoll

多路复用之epoll 一，认识epoll二，epoll的相关接口1. epoll_create2. epoll_ctl3. epoll_wait 三，epoll的原理四，epoll的两种工作模式（ET和LT）1. 两种工作模式2. 对比ET和LT 五，总结 在了解到sel…...

编程日记 2025/6/28 19:42:19

Java 性能调优全解析：从设计模式到 JVM 的 7 大核心方向实践

引言 在高并发、低延迟的技术场景中，Java 性能优化需要系统化的方法论支撑。本文基于7 大核心优化方向（复用优化、计算优化、结果集优化、资源冲突优化、算法优化、高效实现、JVM 优化），结合权威框架与真实案例，构建从…...

编程日记 2025/6/29 0:52:34

“海外滴滴”Uber的Arm迁移实录：重构大规模基础设施​

云工作负载在性价比上的自然演进路径： Intel ➜ AMD ➜ ARM 不信？来看看 Uber 的做法： 01/Arm架构：云计算新时代 2023 年 2 月，Uber 正式开启了一项战略性迁移：将从本地数据中心迁移至云端，…...

编程日记 2025/6/28 9:31:45

java加强 -File

File类的对象可以代表文件/文件夹，并可以调用其提供的方法对象文件进行操作。 File对象既可以代表文件，也可以代表文件夹。 创建File对象，获取某个文件的信息 语法： File 对象名 new File("需要访问文件的绝对路径&…...

编程日记 2025/6/28 23:38:58

SQL注入 ---04

1 简单的sql注入 要求： 要有sql注入： 1，变量 2，变量要带入数据库进行查询 3，没有对变量进行过滤或者过滤不严谨 mysql> select * from users where id2 limit 0,1; 当我的语句这样写时查寻到的结果 当我修改为&…...

编程日记 2025/6/28 22:53:43

MySQL知识点总结（持续更新）

聚合函数通常用于对数据进行统计和聚合操作。以下是一些常见数据库系统（如 MySQL、PostgreSQL、Oracle、SQL Server 等）中常用的聚合函数： 常见的数据库聚合函数： COUNT()：计算指定列中非空值的数量 SELECT COUNT(*) …...

编程日记 2025/6/29 0:01:41

数字信号处理-大实验1.1

MATLAB仿真实验目录 验证实验：常见离散信号产生和实现验证实验：离散系统的时域分析应用实验：语音信号的基音周期（频率）测定 目录 一、常见离散信号产生和实现 1.1 实验目的 1.2 实验要求与内容 1.3 实验…...

编程日记 2025/6/28 22:53:33

Qt操作SQLite数据库教程

Qt 中操作 SQLite 数据库的步骤如下&#xff1a; 1. 添加 SQLite 驱动并打开数据库 #include <QSqlDatabase> #include <QSqlError> #include <QSqlQuery>// 创建数据库连接 QSqlDatabase db QSqlDatabase::addDatabase("QSQLITE"); db.setData…...

编程日记 2025/6/29 0:22:04

【PSINS工具箱】基于工具箱的单独GNSS导航、单独INS导航、两者结合组合导航，三种导航的对比程序。附完整的代码

本文给出基于PSINS工具箱的单独GNSS导航、单独INS导航、两者结合组合导航（153EKF）的程序。并提供三者的轨迹对比、误差对比。 文章目录 运行结果MATLAB代码代码的简单介绍简介2. 平均绝对误差 (MAE)主要模块运行结果 三轴轨迹图： 各轴误差曲线： 命令行窗口的结果输出： …...

编程日记 2025/6/28 22:55:00

开发者的测试复盘：架构分层测试策略与工具链闭环设计实战

摘要‌ 针对测试复盘流于形式、覆盖率虚高等行业痛点&#xff0c;本文提出一套结合架构分层与工具链闭环的解决方案&#xff1a; ‌分层测试策略精准化‌&#xff1a;通过单元测试精准狙击核心逻辑、契约测试驱动接口稳定性、黄金链路固化端到端场景&#xff0c;实现缺陷拦截率…...

编程日记 2025/6/29 0:02:32

手写CString类

学习和理解字符串处理机制&#xff1a;手写 CString 类是深入学习字符串处理和内存管理的有效方式。通过实现构造函数、析构函数、赋值运算符等&#xff0c;能够理解字符串在内存中的存储方式、动态内存分配和释放的原理&#xff0c;以及如何处理字符串的复制、拼接、查找等操作…...

编程日记 2025/6/29 8:49:46

electron结合vue，直接访问静态文件如何跳转访问路径

在最外的app.vue或者index.vue的js模块编写 let refdade ref(1);//刷新&#xff0c;获得请求// 获取完整的查询字符串&#xff08;例如: "?dade/myms"&#xff09;const searchParams new URLSearchParams(window.location.search);// 获取 dade 参数的值&#xf…...

编程日记 2025/6/28 22:53:34

解读RTOS 第七篇 · 驱动框架与中间件集成

1. 引言 在面向生产环境的 RTOS 系统中，硬件驱动框架与中间件层是连接底层外设与上层应用的桥梁。一个模块化、可扩展的驱动框架能够简化外设管理，提升代码可维护性；而丰富的中间件生态则为网络通信、文件系统、图形界面、安全加密等功能提供开箱即用的支持。本章将从驱动模…...

编程日记 2025/6/29 0:04:39

Java GUI开发全攻略：Swing、JavaFX与AWT

Swing 界面开发 Swing 是 Java 中用于创建图形用户界面&#xff08;GUI&#xff09;的库。它提供了丰富的组件&#xff0c;如按钮、文本框、标签等。 import javax.swing.*; import java.awt.event.ActionEvent; import java.awt.event.ActionListener;public class SwingExa…...

编程日记 2025/6/29 0:52:31

Cursor 0.5版本发布，新功能介绍

Cursor，这款流行的AI编程平台，刚刚在其v0.50更新中推出了一系列新功能。 首先，请将您的Cursor IDE更新到最新版本。当您打开Cursor时，您应该会在屏幕左下方收到关于最新版本发布的通知。 更多上下文控制： 对上下文的精细可见性，以及最新模型的MAX模式。 聊天升级： 导出…...

编程日记 2025/6/28 23:49:36

Android学习总结之Glide自定义三级缓存（实战篇）

一、为什么需要三级缓存 内存缓存&#xff08;Memory Cache&#xff09; 内存缓存旨在快速显示刚浏览过的图片&#xff0c;例如在滑动列表时来回切换的图片。在 Glide 中&#xff0c;内存缓存使用 LruCache 算法&#xff08;最近最少使用&#xff09;&#xff0c;能自动清理长…...

编程日记 2025/6/29 1:00:56

Maven 下载安装与配置教程

## 1. Maven 简介 Maven 是一个项目管理和构建自动化工具&#xff0c;主要用于 Java 项目。Maven 可以帮助开发者管理项目的构建、报告和文档&#xff0c;简化项目依赖管理。 ## 2. 下载 Maven 1. 访问 Maven 官方网站 [https://maven.apache.org/download.cgi](https://maven.…...

编程日记 2025/6/28 23:37:07

一篇解决Redis：持久化机制

目录 认识持久化 持久化方案 RDB&#xff08;Redis DataBase&#xff09; 手动触发 自动触发 小结 AOF(Append-Only File) AOF缓冲区刷新机制 AOF重写机制 AOF重写流程 ​编辑 混合持久化 认识持久化 我们都知道Mysql有四大特征&#xff0c;原子性&#xff0c;持久…...

编程日记 2025/6/29 0:28:04

使用IDEA创建Maven版本的web项目以及lombok的使用

1.新建项目 2.修改pom.xml 3.修改项目结构 4.在main/java下面写一个Servlet测试一下 然后当前页面往下滑 -Dfile.encodingUTF-8编写一句输出语句&#xff0c;测试是否成功部署配置&#xff0c;并选择到正确的位置&#xff1a; 回车以后 再回到idea里面&#xff0c;发现控…...

编程日记 2025/6/29 0:12:11

2025年AI开发者在开发者占比？

AI开发者在全球开发者中的占比目前没有一个统一且精确的数值&#xff0c;但根据行业报告和调研数据&#xff0c;可以给出以下大致的范围和趋势分析&#xff1a; 1. 综合估算范围 全球范围&#xff1a;AI/ML&#xff08;机器学习&#xff09;开发者约占开发者总数的 5%-15%&…...

编程日记 2025/6/29 0:11:31

SpringBoot整合MQTT实战：基于EMQX构建高可靠物联网通信，从零到一实现设备云端双向对话

一、引言 随着物联网(IoT)技术的快速发展&#xff0c;MQTT(Message Queuing Telemetry Transport)协议因其轻量级、低功耗和高效的特点&#xff0c;已成为物联网设备通信的事实标准。本文将详细介绍如何使用SpringBoot框架整合MQTT协议&#xff0c;基于开源MQTT代理EMQX实现设…...

编程日记 2025/6/28 3:04:06

Windows更新暂停七天关键注册表

环境&#xff1a;windows10 工具&#xff1a;procmon 下载地址&#xff1a;https://learn.microsoft.com/zh-cn/sysinternals/downloads/procmon 监控截图&#xff1a; 界面截图&#xff1a; 注&#xff1a; 1.北京时间差8小时 2.至少是从第二天恢复&#xff0c;即至少暂停…...

编程日记 2025/6/29 1:30:21

小白学习java第18天（上）：spring

Spring &#xff1a;是一个轻量级&#xff08;一个小依赖就可以实现还不是轻量级&#xff09;的控制反转&#xff08;IOC&#xff09;和面向切面编程&#xff08;AOP&#xff09;的框架&#xff01; 优点&#xff1a; 1.Spring 是一个开源免费的框架&#xff08;容器&#xf…...

编程日记 2025/6/28 23:14:40

用Array.from实现创建一个1-100的数组

一、代码实现 let arr Array.from({length: 100}, (_, i) > i 1); 二、代码分析 1、Array.from(arrayLike, mapFn) &#xff08;1&#xff09;arrayLike 类数组对象&#xff08;如 { length: 100 }&#xff09;本身没有索引属性&#xff08;如 0: undefined, 1: undefi…...

编程日记 2025/6/28 13:15:46

什么是物联网 IoT 平台？

目录 物联网IoT平台的定义 物联网 IoT 平台发展历程 物联网IoT平台数据的特征 物联网IoT平台的处理流程 专为物联网 IoT 平台处理而生的时序数据库 物联网 IoT 平台时序数据处理面临的挑战及解决方案 收益与价值 物联网 IoT 平台企业案例 至数摇光 x TDengine 华自科技…...

编程日记 2025/6/29 0:50:41

PostgREST：无需后端 快速构建RESTful API服务

在现代 Web 开发中&#xff0c;API 已成为连接前后端的核心桥梁&#xff0c;传统的做法是通过后端框架来构建API接口&#xff0c;然后由前后端人员进行联调。 PostgREST是基于无服务器的一种实现方案&#xff0c;允许开发者将PostgreSQL数据库直接暴露为RESTful API&#xff0…...

编程日记 2025/6/29 1:14:18

3天北京旅游规划

北京 第一天应该集中在故宫和市中心区域&#xff0c;比如天安门、人民广场。这样可以体验到北京的历史和政治文化。午餐推荐烤鸭&#xff0c;因为这可是北京的特色。下午可以安排南锣鼓巷&#xff0c;既有古色古香的胡同&#xff0c;又有丰富的美食选择。 第二天的话&#xff0…...

编程日记 2025/6/29 1:23:24

MySQL--day1--数据库概述

&#xff08;以下内容全部来自上述课程&#xff09; 概述 1. 为什么要用数据库 持久化&#xff1a;内存中的数据断电之后就不存在了&#xff0c;所以需要持久化–>需要相关介质。 其中的一个介质就是数据库&#xff1a;存储数据量大、存储数据类型多 2. 数据库与数据库…...

编程日记 2025/6/28 22:54:01

[思维模式-38]：看透事物的关系：什么是事物的关系？事物之间的关系的种类？什么是因果关系？如何通过数学的方式表达因果关系？

一、什么是事物的关系&#xff1f; 事物的关系是指不同事物之间存在的各种联系和相互作用&#xff0c;它反映了事物之间的相互依存、相互影响、相互制约等特性。以下从不同维度为你详细阐述&#xff1a; 1、关系的类型 因果关系 定义&#xff1a;一个事件&#xff08;原因&a…...

编程日记 2025/6/28 22:54:00

图像识别与 OCR 应用实践

图像识别是一种让计算机具备“看”与“理解”图像能力的人工智能技术&#xff0c;其目标是从图像或视频中提取有意义的信息&#xff0c;如物体、人物、场景或文字。在现实生活中&#xff0c;这项技术被广泛应用于面部识别、自动驾驶、安防监控、医疗诊断、图像搜索等多个领域。…...

编程日记 2025/6/28 22:54:02

深入理解卷积神经网络：从基础原理到实战应用

在人工智能领域&#xff0c;卷积神经网络&#xff08;Convolutional Neural Network&#xff0c;简称 CNN&#xff09;凭借其强大的图像识别、处理能力&#xff0c;成为深度学习中不可或缺的技术。无论是自动驾驶汽车识别道路标志&#xff0c;还是医学影像分析辅助疾病诊断&…...

编程日记 2025/6/28 9:45:14

51单片机——交通指示灯控制器设计

设计目标 1、设计一交通灯控制&#xff0c;控制东西方向的红、黄、绿灯和南北方向的红、黄、绿灯。 2、可手动控制和自动控制&#xff0c;设置两个输入控制开关。 手动/自动开关&#xff0c;通过P11的按键输入控制 3、手动&#xff1a;设置开关P11&#xff0c;两种情况&#x…...

编程日记 2025/6/29 0:18:34

vue2 头像上传+裁剪组件封装

背景&#xff1a;最近在进行公司业务开发时&#xff0c;遇到了头像上传限制尺寸的需求&#xff0c;即限制为一寸证件照&#xff08;宽295像素&#xff0c;高413像素&#xff09;。 用到的第三方库&#xff1a; "vue-cropper": "^0.5.5" 完整组件代码&…...

编程日记 2025/6/28 23:39:13

面向对象设计模式之代理模式详解

文章目录 面向对象设计模式之代理模式详解面向对象思想&#xff1a;现代软件开发的基石代理模式&#xff1a;巧妙的中间层设计JavaScript 语法点与代理模式的结合JavaScript 实现代理模式示例代理模式的应用场景 面向对象设计模式之代理模式详解 在现代软件开发的浩瀚领域中&a…...

编程日记 2025/6/28 23:55:52

Leetcode209做题笔记

力扣209 题目分析&#xff1a;想象一个窗口遍历着这个数组&#xff0c;不断扩大右边界&#xff0c;让r。往窗口中添加数字&#xff1a; 此时我们找到了这个窗口&#xff0c;它的和满足了大于等于target的条件&#xff0c;题目让我求最短的&#xff0c;那么我们就尝试来缩短它&…...

编程日记 2025/6/28 7:14:23

SVG 知识详解：从入门到精通

SVG 知识详解&#xff1a;从入门到精通 作为一名前端开发者&#xff0c;我经常会被SVG的魅力所折服。这种基于XML的矢量图形格式&#xff0c;不仅能完美适配各种屏幕分辨率&#xff0c;还能通过CSS和JavaScript进行灵活控制。今天&#xff0c;就让我们一起来深入探索SVG的世界…...

编程日记 2025/6/28 23:41:16

编译openssl源码

openssl版本 1.1.1c windows 安装环境 perl 先安装perl&#xff0c;生成makefile需要 https://strawberryperl.com/releases.html nasm nasm 也是生成makefile需要 https://www.nasm.us/ 安装完perl输入一下nasm&#xff0c;看看能不能找到&#xff0c;找不到的话需要配…...

编程日记 2025/6/28 22:53:51

土壤温湿盐分传感器用于节水农业灌溉引领者三针设计原理便于安装维护

土壤温度部分是由精密铂电阻和高精度变送器两部分组成。变送器部分由电源模块、温度传感模块、变送模块、温度补偿模块及数据处理模块等组成&#xff0c;彻底解决铂电阻因自身特点导入的测量误差&#xff0c;变送器内有零漂电路和温度补偿电路&#xff0c;对使用环境有较高的适…...

编程日记 2025/6/29 0:33:52

Kotlin Compose 与传统 Android UI 开发对比

在移动应用开发领域，Android 开发一直是技术演进的前沿阵地，而 UI 开发作为用户与应用交互的核心环节，其技术体系的变革更是备受瞩目。 技术演进背景 Android UI 开发体系发展脉络 原生 View 体系阶段 在早期的 Android 开发中，原生 View 体系占据了主导地位。开发者通…...

编程日记 2025/6/28 10:55:40

docker-compose——安装redis

文章目录 一、编写docker-compose.yaml文件二、编写redis.conf文件三、启动docker-compose 一、编写docker-compose.yaml文件 version: 3.3 services:redis:image: redis:latestcontainer_name: redisrestart: alwaysports:- 6379:6379volumes:- ./redis/data:/data- ./redis/…...

编程日记 2025/6/28 23:07:23

MFC 调用海康相机进行软触发

初始化相机类文件 #pragma once #include "MvCameraControl.h" class CMvCamera { public:CMvCamera();~CMvCamera();//初始化相机int InitCamera();int SaveCurrentImage(CString filePath);//关闭相机void CloseCamera();//设置int SetEnumValue(IN const char* s…...

编程日记 2025/6/28 23:07:00

第二章 变量和运算符

主要内容 关键字和标识符变量和常量八大基本数据类型Scanner键盘输入基本数据类型的类型转换算术运算符赋值运算符扩展赋值运算符比较运算符逻辑运算符三目运算符运算符的优先级别 学习目标 知识点要求关键字和标识符理解变量和常量掌握八大基本数据类型掌握Scanner键盘输入…...

编程日记 2025/6/28 1:44:44

【starrocks】StarRocks 常见 HTTP 操作与导入错误排查指南

文章目录 一、Stream Load&#xff1a;通过 HTTP 导入数据二、导入状态查询三、取消导入任务四、节点状态监控查看所有 Backend 状态&#xff1a;查看所有 Frontend 状态&#xff1a; 五、导入失败的排查方式1. 查询导入任务状态2. 下载详细错误日志3. 查看 FE/BE 节点日志FE 日…...

编程日记 2025/6/29 0:35:18

网络协议分析 实验七 FTP、HTTP、DHCP

文章目录 实验7.1 FTP协议练习二 使用浏览器登入FTP练习三 在窗口模式下&#xff0c;上传/下传数据文件实验7.2 HTTP(Hyper Text Transfer Protocol)练习二 页面提交练习三 访问比较复杂的主页实验7.3 DHCP(Dynamic Host Configuration Protocol) 实验7.1 FTP协议 dir LIST&…...

编程日记 2025/6/29 0:00:01

ET ProcessInnerSender类(实体) 分析

ProcessInnerSender 作用是进程内部发送Actor消息 字段 TIMEOUT_TIME 超时时间RpcId 用来累加requestCallback 存储RPC的回调事件list 用来获取MessageQueue中的Actor消息 方法 Awake 初始化在MessageQueue中注册待处理的消息队列Destroy 移除在MessageQueue中的消息队列U…...

编程日记 2025/6/29 0:13:57

远程连接工具

绿色轻便ToDesk https://www.todesk.com/download.html 向日葵 https://sunlogin.oray.com/download...

编程日记 2025/6/29 0:23:07

MySQL库级管理：数据库管理与存储引擎剖析

引言 各位数据库爱好者们好&#xff01;今天我们要深入探讨MySQL数据库的基本操作&#xff0c;这是每位开发者必须掌握的"内功心法" &#x1f4aa;。无论你是刚接触MySQL的小白&#xff0c;还是需要复习基础的老手&#xff0c;这篇教程都将带你系统学习数据库的核心…...

编程日记 2025/6/28 23:45:05