Leetcode 每日一题 290.单词规律

目录

一、问题分析

二、解题思路

三、代码实现

四、复杂度分析

五、总结


在编程的世界里,我们常常会遇到各种有趣的字符串匹配问题。今天要探讨的就是这样一个问题:给定一种规律 pattern 和一个字符串 s,判断 s 是否遵循与 pattern 相同的规律。这里的 “遵循” 意味着 pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

一、问题分析

首先,我们明确一下问题的关键要求:

  • pattern 仅包含小写英文字母,其长度范围是 1 <= pattern.length <= 300
  • s 包含小写英文字母和空格,且不包含前导或尾随空格,每个单词由单个空格分隔,长度范围是 1 <= s.length <= 3000
  • pattern 与 s 之间的对应关系必须是双向的,即一个字母对应一个特定单词,且一个单词也只能对应一个特定字母。

二、解题思路

为了判断这种双向对应关系,我们可以利用两个哈希表来分别记录从 pattern 中的字符到 s 中的单词的映射,以及从 s 中的单词到 pattern 中的字符的映射。

  1. 首先,将字符串 s 按照空格进行分割,得到一个单词数组 ss。如果 pattern 的长度与 ss 的长度不相等,那么直接返回 false,因为它们不可能存在一一对应的关系。
  2. 然后,遍历 pattern 和 ss,对于每一个位置 i
    • 将 pattern 中的字符作为键,ss 中的单词作为值存入 map 哈希表。
    • 将 ss 中的单词作为键,pattern 中的字符作为值存入 map1 哈希表。
  3. 最后,再次遍历 pattern 和 ss,检查 map 和 map1 中的映射关系是否正确。如果在任何位置发现不匹配的情况,即 map 中通过字符获取的单词与实际的 ss[i] 不相等,或者 map1 中通过单词获取的字符与实际的 pattern.charAt(i) 不相等,就返回 false。如果整个遍历过程都没有发现不匹配,那么说明 s 遵循 pattern 的规律,返回 true

过题图片

三、代码实现

以下是使用 Java 实现的代码:

class Solution {public boolean wordPattern(String pattern, String s) {// 用于存储从 pattern 中的字符到 s 中的单词的映射HashMap<Character,String> map = new HashMap<>();// 用于存储从 s 中的单词到 pattern 中的字符的映射HashMap<String,Character> map1 = new HashMap<>();// 将 s 按照空格分割成单词数组String[] ss = s.split(" ");// 如果 pattern 长度与单词数组长度不相等,直接返回 falseif(pattern.length()!= ss.length) return false;// 遍历 pattern 和单词数组,建立双向映射for(int i = 0; i < pattern.length(); i++){map.put(pattern.charAt(i), ss[i]);map1.put(ss[i], pattern.charAt(i));}// 再次遍历,检查映射关系是否正确for(int i = 0; i < pattern.length(); i++){if(!map.get(pattern.charAt(i)).equals(ss[i])){return false;}if(!map1.get(ss[i]).equals(pattern.charAt(i))){return false;}}return true;}
}

四、复杂度分析

  • 时间复杂度:主要的操作是对 pattern 和 ss 进行两次遍历。第一次遍历用于建立哈希表,时间复杂度为 ,其中  是 pattern 的长度(也是 ss 的长度)。第二次遍历用于检查映射关系,时间复杂度也为 。所以总的时间复杂度为 。
  • 空间复杂度:需要创建两个哈希表来存储映射关系,在最坏情况下,哈希表中可能存储 pattern 中的所有字符和 ss 中的所有单词,所以空间复杂度为 ,其中  是 pattern 的长度(也是 ss 的长度)。

题目链接

290. 单词规律 - 力扣(LeetCode)

五、总结

题目要求判断字符串 s 与给定的规律 pattern 是否完全匹配,这里的匹配是一种双向连接的对应关系,即 pattern 里的每个字母要和 s 中的每个非空单词一一对应,且反之亦然。同时,题目对 pattern 和 s 的长度、字符组成以及 s 的单词分隔形式等都做了相应限定,明确这些要求是正确解题的基础。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

浅谈FRTC8563M实时时钟芯片

FRTC8563M是NYFEA徕飞公司推出的一款实时时钟芯片和日历芯片&#xff0c;采用MSOP-8封装形式。它具有低功耗特性&#xff0c;适用于电池供电的便携式设备。该芯片提供年、月、日、星期、小时、分钟和秒的计时功能&#xff0c;并且具有闹钟功能。FRTC8563M通过I2C总线与微控制器…

HOC vs Render Props vs Hooks

相关问题 什么是 HOC / Render Props / Hooks为什么需要 HOC / Render Props / Hooks如何提高代码复用性Hooks 的实现原理Hooks 相比其他方案有什么优势 关键点 复用性HOC / Render Props / Hooks 三种写法都可以提高代码的复用性&#xff0c;但实现方法不同&#xff1a; H…

【每天一篇深度学习论文】2024多级卷积模块MCM

目录 论文介绍题目&#xff1a;论文地址&#xff1a; 创新点方法模型总体架构双流编码器特征融合模块解码器 核心模块描述多尺度感知融合模块&#xff08;MAFM&#xff09;全局融合模块&#xff08;GFM&#xff09;多级卷积模块&#xff08;MCM&#xff09; 即插即用模块作用特…

Play with docker 使用ssh命令远程登录时Permission denied (publickey)

可以看到这里使用的是 ssh-ed25519 在本机生成对应密钥: ssh-keygen -t ed25519 -P "" -f ~/.ssh/id_ed25519 然后再尝试远程连接就好了。 参考:无法通过SSH连接到码头游乐场中的实例-腾讯云开发者社区-腾讯云

我眼中的“懂重构”(一)

初识重构 2017年的时候&#xff0c;领导让我看公司的一本书《重构——改善代码的既有设计》&#xff0c;这是一本JAVA版本的&#xff0c;前后看了2遍。那时候看书因为不懂看的格外仔细。我只是那时候不懂&#xff0c;然而多年后的今天我仍然发现很多人对重构充满误解。在刚进入…

数字图像处理(15):图像灰度反转和彩色反转

&#xff08;1&#xff09;图像反转&#xff1a;是指对图像的颜色信息进行相反的处理&#xff0c;从而得到一个新的图像。在计算机视觉和图像处理领域&#xff0c;图像反转是一种常见的操作&#xff0c;它可以帮助我们实现不同的图像特效和视觉效果。 &#xff08;2&#xff09…

Ubuntu系统上mysql服务部署

前段时间搞了一个mysql服务端的部署&#xff0c;在Ubuntu系统上&#xff0c;中间也踩了许多坑&#xff0c;特此记录下。 下载 官网&#xff1a;MySQL :: MySQL Community Downloads 这个里面有不同系统的安装包&#xff0c;根据自己的系统选择&#xff0c;我选了 MySQL Com…

linux 服务器 一次性查看 CPU、内存和磁盘使用情况

创建 vi check_usage.sh #!/bin/bashecho " CPU 使用率 " mpstat -P ALL 1 1echo -e "\n 内存使用情况 " free -hecho -e "\n 磁盘使用率 " df -h执行授权 chmod x check_usage.sh执行查看 ./check_usage.sh这样可以快速获取系统资源的概览。…

Unity HDRP Water Surface 水系统 基础教程

Unity HDRP Water Surface 水系统 基础教程 Unity Water SurfaceUnity 项目创建Unity Water Surface&#xff1a;Ocean&#xff08;海洋&#xff09;简介Ocean&#xff1a;Transform、GeneralOcean&#xff1a;Simulation&#xff08;仿真模拟&#xff09;Ocean&#xff1a;Sim…

【Golang】Golang基础语法(三):常量

常量 Golang 语言当中常量的定义和其它语言类似。 const filename_in_package string "abc.txt" // 可以定义为包内常量func consts() {const filename string "abc.txt" // 可以为常量规定类型const a, b 3, 4 // 也可以不规定const…

Cesium-环境搭建

安装步骤 1.安装node.js 2.去Cesium官网下载源码包 other:npm install Cesium 通过这种方式装 ,没有装成功,主要错误提示说缺少gulp文件,具体错误如下 ​ [1/5] Validating package.json... [2/5] Resolving packages... success Already up-to-date. $ gulp prepare &a…

mysql基础学习1

useradd -r -g mysql -s /bin/false mysql (-r)系统用户 不能登录 A temporary password is generated for rootlocalhost: d>#jT7rfoaz) 看是否启动 看进程 端口 直接连接 看日志 varchar (20) char(20)更耗空间 create table student_info(id int,name varchar(20),s…

行业Know-How助力零售企业数字化转型|StartDT Talk

【StartDT Talk】“客户成功三要素”系列直播第三期圆满收官&#xff01; 本期直播聚焦于三要素之一的“好的行业Know-How”&#xff08;行业理解&#xff09;&#xff0c;由奇点云创始人行在和资深产研专家追风共同探讨与零售相关的行业知识&#xff0c;以及我们在零售行业的…

linux——进程间通信system V消息队列

Linux——命名管道及日志-CSDN博客 文章目录 目录 文章目录 前言 一、system V消息队列是什么&#xff1f; 二、相关库接口 1.shmget接口 2、ftok接口 3、shmget、ftok接口封装 4、共享内存操作 ​编辑 5、shmdt接口 三.函数的调用 1、查看共享内存 2、shell 四…

【Redis】not support: redis

1、查看redis进程 2、查看是否安装redis扩展&#xff0c;此处以宝塔为例

网站维护记录

服务器重启&#xff0c;网站打不开&#xff1a;chown -R manager:manager /run/php-fpm/www.sock wordpress升级需设置ftp&#xff1a; // 设置权限0777 //define("FS_METHOD", "direct"); //define("FS_CHMOD_DIR", 0777); //define("…

XiYan-SQL:⼀种多⽣成器集成的Text-to-SQL框架

发布于:2024 年 12 月 03 日 星期二 北京 #NL2SQL #阿里巴巴 #Text-to-SQL 文提出了一种用于自然语言到 SQL 转换的多生成器集成框架 ——XiYan-SQL,旨在应对大型语言模型在 NL2SQL 任务中的挑战。该框架融合提示工程与监督微调(SFT)方法,利用 SFT 的可控性与上下文学习(…

283.移动零(快慢指针)

目录 题目过程解法 题目 给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。 过程 class Solution { public:void moveZeroes(vector<int…

L17.【LeetCode笔记】另一棵树的子树

目录 1.题目 代码模板 2.分析 3.代码 4.提交结果 1.题目 https://leetcode.cn/problems/subtree-of-another-tree/description/ 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在&#xff0c;返回 true &#xff…

天天AI-241302:今日热点-B站第二届超级科学晚聚焦AIGC,年度播放量突破300亿次

2AGI.NET 天天 AI 天天AI&#xff1a;AIGC技术引领科学与媒体新浪潮天天AI&#xff1a;AIGC技术引领科学与媒体新浪潮https://www.2agi.net/blog/daily-ai-aigc-technology-leads-science-and-media-new-wave/ 1. B站第二届超级科学晚聚焦AIGC&#xff0c;年度播放量突破300亿…