634 · 单词矩阵

链接:LintCode 炼码 - ChatGPT!更高效的学习体验!

. - 力扣(LeetCode)

题解:

class Solution {
public:
struct Trie {Trie() {next.resize(26, nullptr);end = false;}
std::vector<Trie*> next;
bool end;
};
Trie* insert_trie(vector<string>& words) {Trie* root = new (std::nothrow)Trie;for (auto& word : words) {Trie* cur = root;for (int i = 0; i < word.size(); ++i) {if (cur->next[word[i]-'a'] == nullptr) {cur->next[word[i]-'a'] = new (std::nothrow) Trie;}cur = cur->next[word[i]-'a'];}cur->end = true;}return root;
}vector<string> maxRectangle(vector<string>& words) {if (words.size() <= 0) {return {};}Trie* root = insert_trie(words);if (!root) {return {};}// 构建相同长度的表int max_word_len = 0; // std::unordered_map<int, std::unordered_set<string>> len2words;for (auto& word : words) {int len = word.size();max_word_len = max(max_word_len, len);len2words[len].insert(word);}// 回溯// 最终结果,总共字符串的长度int max_len = 0;// 记录回溯路径std::vector<string> path;// 记录最终结果std::vector<string> result;for (auto& entry : len2words) {path.clear();dfs(root, entry.first, entry.second, path, result, max_len, max_word_len);}return result;}
private:void dfs(Trie* root, int len, unordered_set<string>& words,std::vector<std::string>& path,std::vector<std::string>& result,int& max_len,int max_word_len) {// 如果当前字符的长度*宽度比最大的小,直接返回,剪枝if (len * len <= max_len) {return;}for (auto& word : words) {// 把当前字符追加到路径 中path.push_back(word);// 判断已经追加的字符串是否是正确额度auto valid = is_valid(path, root);if (valid.first) {// 获得字符串矩形的面积int tmp_len = path[0].size() * path.size();if (valid.second && tmp_len > max_len) {// 记录最大面积max_len = tmp_len;std::vector<string> tmp(path);result = std::move(tmp);}// 递归下一层dfs(root, len, words, path, result, max_len, max_word_len);}// 回溯path.pop_back();}}std::pair<int, int> is_valid(std::vector<std::string>& path, Trie* root) {int word_len = path[0].size();int row_size = path.size();bool allend = true;/*for (auto& tmp : path) {cout << tmp << " ";}cout << endl;*/// 判断字符矩阵,按照列查看是否,字符串在字典树中for (int i = 0; i < word_len; ++i) {Trie* cur = root;for (int j = 0; j < row_size; ++j) {if (cur->next[path[j][i]-'a'] == nullptr) {return std::pair<int, int>(false, false);}cur = cur->next[path[j][i]-'a'];}// 如果当前字符不是结尾if (!cur->end) {allend = false;}}//cout << " ====" << endl;return std::pair<int, int>(true , allend);}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/331163.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python高级进阶--dict字典

dict字典⭐⭐ 1. 字典简介 dictionary&#xff08;字典&#xff09; 是 除列表以外 Python 之中 最灵活 的数据类型&#xff0c;类型为dict 字典同样可以用来存储多个数据字典使用键值对存储数据 2. 字典的定义 字典用{}定义键值对之间使用,分隔键和值之间使用:分隔 d {中…

DT浏览器有一些特点和优势,可能是人们选择使用的原因

DT浏览器有一些特点和优势&#xff0c;可能是人们选择使用的原因&#xff1a; - 好评如潮&#xff1a;DT浏览器在网络上获得了众多用户的好评&#xff0c;口碑良好。 - 使用微软搜索引擎技术&#xff1a;DT浏览器采用了微软的搜索引擎技术&#xff0c;在搜索内容上提供了国内…

Unity 实现心电图波形播放(需波形图图片)

实现 在Hierarchy 面板从2D Object 中新建一个Sprite&#xff0c;将波形图图片的赋给Sprite。 修改Sprite 的Sprite Renderer 组件中Draw Mode 为Tiled, 修改Sprite Renderer 的Size 即可实现波形图播放。 在Hierarchy 面板从2D Object 中新建一个Sprite Mask 并赋以遮罩图片…

【qt】标准型模型 下

标准型模型 一.前言二.预览数据1.获取表头2.获取数据项 三.保存文件1.文件对话框获取保存文件名2.用文件名初始化文件对象3.打开文件对象4.用文件对象初始化文本流5.写入数据 四.格式1.居右2.居中3.居左4.粗体 五.模型的信号1.解决粗体action问题2.状态栏显示信息 六.总结 一.前…

HarmonyOS鸿蒙应用开发——安装与配置

今天脑子又抽风&#xff0c;前端转完学后端之后&#xff0c;今天大周末早上醒来突然又想学鸿蒙了&#xff0c;刚好有个比赛需要用到鸿蒙&#xff0c;于是乎我就随便点开b站看了一下鸿蒙视频&#xff0c;然后马上来写这篇博客&#xff0c;后续我的鸿蒙的博客可能会跳着、不连续地…

【Apache Doris】周FAQ集锦:第 4 期

【Apache Doris】周FAQ集锦&#xff1a;第 4 期 SQL问题数据操作问题运维常见问题其它问题关于社区 欢迎查阅本周的 Apache Doris 社区 FAQ 栏目&#xff01; 在这个栏目中&#xff0c;每周将筛选社区反馈的热门问题和话题&#xff0c;重点回答并进行深入探讨。旨在为广大用户和…

学AI绘图【300集SD新课】--Stable Diffusion教程

学AI绘图需要以下步骤&#xff1a; 明确目标和需求&#xff1a;首先明确设计图的目的&#xff0c;是用于展示算法流程、模型结构还是其他目的。选择合适的工具&#xff1a;根据需求选择合适的绘图工具&#xff0c;如Visio、PowerPoint、Adobe Illustrator等。绘制草图&#xf…

uni-app 微信 支付宝 小程序 使用 longpress 实现长按删除功能,非常简单 只需两步

1、先看效果 2、直接上代码 ui结构 <view class"bind" longpress"deleteImage" :data-index"index"><view class"bind_left">绑定设备</view><view class"bind_right"><view class"bind_t…

5.24学习记录

[FSCTF 2023]ez_php2 比较简单的pop链 <?php highlight_file(__file__); Class Rd{public $ending;public $cl;public $poc;public function __destruct(){echo "All matters have concluded";die($this->ending);}public function __call($name, $arg){for…

Linux服务器安装docker,基于Linux(openEuler、CentOS8)

本实验环境为openEuler系统(以server方式安装)&#xff08;CentOS8基本一致&#xff0c;可参考本文) 目录 知识点实验 知识点 实验 查看yum源docker版本 dnf search docker安装docker dnf install dockerdocker --version

VScode SSH连接远程服务器报错

一、报错 通过VScode SSH插件远程连接服务器&#xff0c;输入密码后没有连接成功&#xff0c;一直跳出输入密码界面&#xff0c;在输出界面里&#xff0c;一直是Waiting for server log或者是显示Cannot not find minimist 二、处理 &#x1f431;&#xff1a; 这个时候应该…

【2024最新华为OD-C卷试题汇总】传递悄悄话的最长时间(100分) - 三语言AC题解(Python/Java/Cpp)

&#x1f36d; 大家好这里是清隆学长 &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C卷的三语言AC题解 &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x1f497; 文章目录 前…

42-2 应急响应之计划任务排查

一、进程排查 进程排查是指通过分析系统中正在运行的进程,以识别和处理恶意程序或异常行为。在Windows和Linux系统中,进程是操作系统的基本单位,因此对于发现和处理恶意软件或异常活动至关重要。恶意程序通常会以进程的形式在系统中运行,执行各种恶意操作,比如窃取信息、破…

自定义RedisTemplate序列化器

大纲 RedisSerializerFastJsonRedisSerializer自定义二进制序列化器总结代码 在《RedisTemplate保存二进制数据的方法》一文中&#xff0c;我们将Java对象通过《使用java.io库序列化Java对象》中介绍的方法转换为二进制数组&#xff0c;然后保存到Redis中。实际可以通过定制Red…

Leetcode刷题笔记2

283. 移动零 283. 移动零 - 力扣&#xff08;LeetCode&#xff09; 数据划分、数据分块 利用数组下标充当指针cur&#xff1a;从左往右扫描数组&#xff0c;遍历数组dest&#xff1a;已处理的区间内&#xff0c;非零元素的最后一个位置 一共被分为三个区间 [0,dest] [dest1,cu…

42-3 应急响应之服务排查

一、服务排查 服务是后台运行的进程,可在计算机启动时自动启动,也可暂停和重新启动,且不显示用户界面。它们特别适用于长时间运行的功能,以避免影响其他用户在同一台计算机上的工作。在应急响应中,服务常被恶意软件用作驻留方法。 二、Windows服务排查 打开【运行】对话框…

【C++项目】实时聊天的在线匹配五子棋对战游戏

目录 项目介绍 开发环境 核心技术 项目前置知识点介绍 Websocketpp 1. WebSocket基本认识 2. WebSocket协议切换原理解析 3. WebSocket报文格式 4. Websocketpp介绍 5. 搭建一个简单WebSocket服务器 JsonCpp 1. Json格式的基本认识 2. JsonCpp介绍 3. 序列化与反序…

iPhone实况照片从Windows资源管理器复制的JPG+MOV无法正常还原到iPhone

背景&#xff1a; 之前使用的iPhone 15 Pro&#xff0c;使用的Windows资源管理器当中复制导出的实况照片&#xff0c;复制出来的格式例如IMG_0001.JPG, IMG_0001.MOV。之后手机就卖掉了。现在使用的iPhone 14 Pro Max&#xff0c;想要导回之前备份的实况照片。尝试使用爱思助手…

VBA即用型代码手册:删除Excel中空白行Delete Blank Rows in Excel

我给VBA下的定义&#xff1a;VBA是个人小型自动化处理的有效工具。可以大大提高自己的劳动效率&#xff0c;而且可以提高数据的准确性。我这里专注VBA,将我多年的经验汇集在VBA系列九套教程中。 作为我的学员要利用我的积木编程思想&#xff0c;积木编程最重要的是积木如何搭建…

一篇文章讲透排序算法之希尔排序

希尔排序是对插入排序的优化&#xff0c;如果你不了解插入排序的话&#xff0c;可以先阅读这篇文章&#xff1a;插入排序 目录 1.插入排序的问题 2.希尔排序的思路 3.希尔排序的实现 4.希尔排序的优化 5.希尔排序的时间复杂度 1.插入排序的问题 如果用插入排序对一个逆序…