LeetCode //C - 290. Word Pattern
290. Word Pattern
Given a pattern and a string s, find if s follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.
Example 1:
Input: pattern = “abba”, s = “dog cat cat dog”
Output: true
Example 2:
Input: pattern = “abba”, s = “dog cat cat fish”
Output: false
Example 3:
Input: pattern = “aaaa”, s = “dog cat cat dog”
Output: false
Constraints:
- 1 <= pattern.length <= 300
- pattern contains only lower-case English letters.
- 1 <= s.length <= 3000
- s contains only lowercase English letters and spaces ’ '.
- s does not contain any leading or trailing spaces.
- All the words in s are separated by a single space.
From: LeetCode
Link: 290. Word Pattern
Solution:
Ideas:
The code for the wordPattern function is designed to determine whether a given string s follows a specific pattern. Here’s a breakdown of the idea behind the code:
-
Initialization: The code initializes an array of pointers words, where each index corresponds to a lowercase letter in the pattern (from ‘a’ to ‘z’). This array will be used to track the mapping between each character in the pattern and a corresponding word in the string s.
-
String Copy: Since the code utilizes strtok to tokenize the string s, which alters the original string, a copy of the string is made to preserve the input.
-
Tokenization and Mapping: The code tokenizes the string s into words and iterates through these words alongside the characters in the pattern:
- If the pattern is exhausted before all words are processed, the function returns false, as there is a mismatch in length.
- For each character in the pattern, the code checks whether it has been mapped to a word before. If not, it verifies that no other character has been mapped to the current word (to ensure a bijection). If all is well, the current character is mapped to the current word.
- If the character has already been mapped to a word, the code checks that this word matches the current word in the string. If there’s a mismatch, the function returns false.
-
Length Check: After processing all words, the code checks whether the pattern’s length matches the number of words. If there’s a mismatch, the function returns false.
-
Result: If all checks pass, the function returns true, indicating that the string s follows the given pattern.
Code:
bool wordPattern(char * pattern, char * s) {char *words[26];for (int i = 0; i < 26; i++) words[i] = NULL;char *s_copy = strdup(s);char *token = strtok(s_copy, " ");int i = 0;while (token != NULL) {// If the pattern is shorter than the number of words, return falseif (i >= strlen(pattern)) {free(s_copy);return false;}int idx = pattern[i] - 'a';if (words[idx] == NULL) {// Check if any other character maps to the same wordfor (int j = 0; j < 26; j++) {if (words[j] && strcmp(words[j], token) == 0) {free(s_copy);return false;}}words[idx] = token;} else {if (strcmp(words[idx], token) != 0) {free(s_copy);return false; // Mismatch in mapping}}token = strtok(NULL, " ");i++;}free(s_copy);// Check if pattern length matches the number of wordsif (i != strlen(pattern)) return false;return true;
}
相关文章:
LeetCode //C - 290. Word Pattern
290. Word Pattern Given a pattern and a string s, find if s follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s. Example 1: Input: pattern “abba”, s “dog c…...
[保研/考研机试] 括号匹配问题 C++实现
题目描述: 在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序,找到无法匹配的左括号和右括号,输出原来的字符串&am…...
springBoot集成caffeine,自定义缓存配置 CacheManager
目录 springboot集成caffeine Maven依赖 配置信息:properties文件 config配置 使用案例 Caffeine定制化配置多个cachemanager springboot集成redis并且定制化配置cachemanager springboot集成caffeine Caffeine是一种基于服务器内存的缓存库。它将数据存储在…...
【瑞吉外卖】Git部分学习
Git简介 Git是一个分布式版本控制工具,通常用来对软件开发过程中的源代码文件进行管理。通过Git仓库来存储和管理这些文件,Git仓库分为两种: 本地仓库:开发人员自己电脑上的Git仓库 远程仓库:远程服务器上的Git仓库…...
如何阐述自己做了一个什么样的东西
线上qps2000,主要的性能瓶颈在于出现在数据库I/O上。另外,如果是一个正常部署的容器,qps能达到几百就不错了。资讯服务现在做了静态的底层页,所以热点新闻多数会命中底层页,即便没有命中底层页,也会走多层的…...
TC3XX - MCAL知识点(二十二):QSPI 同步与异步 Mcal配置及代码实战
目录 1、MCAL配置 1.1、配置目标 1.2、同步QSPI配置 1.2.1、SpiGeneral 1.2.2、SpiMaxChannel 1.2.3、SpiMaxJob...
led台灯哪些牌子性价比高?推荐几款性价比高的护眼台灯
作为学龄期儿童的家长,最担心的就是孩子长时间学习影响视力健康。无论是上网课、写作业、玩桌游还是陪伴孩子读绘本,都需要一个足够明亮的照明环境,因此选购一款为孩子视力发展保驾护航的台灯非常重要。为大家推荐几款性价比高的护眼台灯。 …...
什么情况下容易发生锁表及如何处理
目录 什么情况下容易发生锁表发生锁表怎么解决 什么情况下容易发生锁表 在数据库中,当多个事务同时竞争访问同一个表的资源时,可能会发生锁表现象,导致性能下降甚至阻塞。以下情况容易导致锁表问题: 大事务操作:如果一…...
elk开启组件监控
elk开启组件监控 效果: logstash配置 /etc/logstash/logstash.yml rootnode1:~# grep -Ev "^#|^$" /etc/logstash/logstash.yml path.data: /var/lib/logstash path.logs: /var/log/logstash xpack.monitoring.enabled: true xpack.monitoring.elasti…...
Java Random 类的使用
Java中的Random类是用来生成伪随机数的工具类。它可以用来生成随机的整数、浮点数和布尔值。以下是Java Random类的一些常见用法: 创建Random对象: Random random new Random();生成随机整数: int randomNumber random.nextInt(); // 生…...
完美的分布式监控系统——Prometheus(普罗米修斯)与优雅的开源可视化平台——Grafana(格鲁夫娜)
一、基本概念 1、之间的关系 prometheus与grafana之间是相辅相成的关系。作为完美的分布式监控系统的Prometheus,就想布加迪威龙一样示例和动力强劲。在猛的车也少不了仪表盘来观察。于是优雅的可视化平台Grafana出现了。 简而言之Grafana作为可视化的平台ÿ…...
pycharm的Terminal中如何设置打开anaconda3的虚拟环境
在pycharm的File -> Settings -> Tools -> Terminal下面,如下图所示 修改为红框中内容,然后关闭终端在重新打开终端,即可看到anaconda3的虚拟环境就已经会被更新...
Jmeter(四) - 从入门到精通 - 创建网络测试计划(详解教程)
1.简介 在本节中,您将学习如何创建基本的 测试计划来测试网站。您将创建五个用户,这些用户将请求发送到JMeter网站上的两个页面。另外,您将告诉用户两次运行测试。因此,请求总数为(5个用户)x(2…...
Flowable-结束事件-空结束事件
目录 定义图形标记XML内容 定义 空结束事件是最常见的一种结束事件,也是最简单的一种结束事件,只要把结束任务置于流程 或分支的最后节点,流程实例运行到该节点的时候,流程引擎就会结束该流程实例或分支。前面提 到,结…...
Elasticsearch:如何创建 Elasticsearch PEM 和/或 P12 证书?
你是否希望使用 SSL/TLS 证书来保护你的 Elasticsearch 部署? 在本文中,我们将指导你完成为 Elasticsearch 创建 PEM 和 P12 证书的过程。 这些证书在建立安全连接和确保 Elasticsearch 集群的完整性方面发挥着至关重要的作用。 友情提示:你可…...
数仓架构模型设计参考
1、数据技术架构 1.1、技术架构 1.2、数据分层 将数据仓库分为三层,自下而上为:数据引入层(ODS,Operation Data Store)、数据公共层(CDM,Common Data Model)和数据应用层ÿ…...
RedisTemplate.opsForGeo()用法简介并举例
RedisTemplate.opsForGeo()是RedisTemplate类提供的用于操作Geo类型(地理位置)的方法。它可以用于对Redis中的Geo数据结构进行各种操作,如添加地理位置、获取距离、获取位置信息等。 下面是一些常用的RedisTemplate.opsForGeo()方法及其用法…...
Android OkHttp源码分析--拦截器
拦截器责任链: OkHttp最核心的工作是在 getResponseWithInterceptorChain() 中进行,在进入这个方法分析之前,我们先来了 解什么是责任链模式,因为此方法就是利用的责任链模式完成一步步的请求。 拦截器流程: OkHtt…...
docker:如何传环境变量给entrypoint
使用shell,不带中括号 ENTRYPOINT .\main -web -c $CONFIGENTRYPOINT [sh, -c, ".\main -web -c $CONFIG"]docker build --build-arg ENVIROMENTintegration // 覆盖ENTRYPOINT命令 使用shell脚本 ENTRYPOINT ["./entrypoint.sh"]entrypoint.sh 镜像是a…...
kuboard安装和使用
windows平台下使用docker和docker-compose部署Kuboard,并添加Docker Desktop for windows的k8s单机集群 使用docker安装 docker run -d \--restartunless-stopped \--namekuboard \-p 80:80/tcp \-p 10081:10081/tcp \-e KUBOARD_ENDPOINT"http://内网IP:80&…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
