《程序员面试金典(第6版)》面试题 16.18. 模式匹配(暴力破解 + 剪枝)
题目描述
你有两个字符串,即pattern和value。 pattern字符串由字母"a"和"b"组成,用于描述字符串中的模式。
例如,字符串"catcatgocatgo"匹配模式"aabab"(其中"cat"是"a",“go"是"b”),
该字符串也匹配像"a"、"ab"和"b"这样的模式。
但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。
示例 1:
输入: pattern = "abba", value = "dogcatcatdog"
输出: true
示例 2:
输入: pattern = "abba", value = "dogcatcatfish"
输出: false
示例 3:
输入: pattern = "aaaa", value = "dogcatcatdog"
输出: false
示例 4:
输入: pattern = "abba", value = "dogdogdogdog"
输出: true
解释: "a"="dogdog",b="",反之也符合规则
提示:
- 1 <= len(pattern) <= 1000
- 0 <= len(value) <= 1000
- 你可以假设pattern只包含字母"a"和"b",value仅包含小写字母。
解题思路与代码(暴力破解 + 剪枝)
这道题的核心其实就只有一个问题。就是如何去用a,b匹配到对应的单词,匹配到返回true,匹配不到返回false。
- 那么如何匹配呢?首先我们要去搞清楚一个问题,那就是a有多少个,b有多少个。
- 这么做的目的是确定a,b在对应的字符串中匹配的范围,为的其实就是在最后匹配的环节中,不要去做无用的匹配。
- 这里我们还有去做一步优化,那就是要使a的数量永远大于等于b。如果a的数量大于b,那么就交换a与b的数量,与模式串中的字符。
- 之后我们用一个for循环,开始划定a匹配字符的范围。
a的范围 = value.size() / a的个数。那么b的范围其实就是value剩下的再去除以b的个数。 - 最后我们用一个check函数,去检查字符有没有匹配成功的,如果有,我们就返回true,没有则就是false。
这道题的思路大致上就是这样。其实关于边界范围与具体如何检查我没有细讲。但这其实不算是代码的核心逻辑部分了。只要你用点心也就都能想出来。如果还是有点问题。那就请看我的代码吧~
具体代码如下:
class Solution {
public:bool patternMatching(string pattern, string value) {// 创建两个变量a,b,并且使a的数量永远大于b的数量int aCount = 0;int bCount = 0;for(char &a : pattern)if(a == 'a') ++aCount;else ++bCount;if(aCount < bCount){swap(aCount,bCount);for(char &a : pattern)if(a == 'a') a = 'b';else a = 'a';}if(value.size() == 0) return bCount == 0; for(int i = 0; i * aCount <= value.size(); ++i){ // 先确定模式a匹配的字符范围,剩下的便是b匹配的字符范围int rest = value.size() - aCount * i; // 所有的b平分rest里面的字符if((rest == 0 && bCount == 0) || (bCount != 0 && rest % bCount == 0)){int len_b = (bCount == 0 ? 0 : rest / bCount);if(check(pattern,value,i,len_b)) return true;}}return false;}bool check(string& pattern, string& value, int& aLength, int bLength){string a = "";string b = "";int pos = 0;for(char& c : pattern){if(c == 'a'){string str = value.substr(pos,aLength);if(a.empty()) a = str;else if(a != str) return false;pos += aLength;}else{string str = value.substr(pos,bLength);if(b.empty()) b = str;else if(b != str) return false;pos += bLength;}}return a != b;}
};

总结
这道题目的主要意义在于考察程序员处理字符串模式匹配的能力,以及对算法复杂度优化的理解。
-
字符串模式匹配:这是一个在实际编程中非常常见的问题,例如在文本编辑器的查找和替换功能、正则表达式匹配等场景中都需要处理这类问题。这道题目要求考察者根据给定的模式,找出一个或两个子串(对应模式中的 ‘a’ 和 ‘b’)来使得整个字符串满足该模式,这需要考察者对字符串操作的熟练程度以及对模式匹配问题的理解。
-
算法复杂度优化:这道题目在不进行优化的情况下,最直接的解法可能会涉及到对所有可能的 ‘a’ 和 ‘b’ 的长度组合进行枚举,这会导致时间复杂度过高。因此,考察者需要理解如何通过统计 ‘a’ 和 ‘b’ 的数量、控制 ‘a’ 和 ‘b’ 的长度范围等方法来降低算法的复杂度。
-
边界情况处理:这道题目的输入中 ‘a’ 和 ‘b’ 可以对应空字符串,这增加了问题的复杂性。处理这类问题需要考察者对边界情况的敏感度和处理能力。
综上,这道题目的意义主要在于考察程序员的实际编程能力、对算法复杂度的理解以及对边界情况的处理能力。
最后的最后,如果你觉得我的这篇文章写的不错的话,请给我一个赞与收藏,关注我,我会继续给大家带来更多更优质的干货内容。
相关文章:
《程序员面试金典(第6版)》面试题 16.18. 模式匹配(暴力破解 + 剪枝)
题目描述 你有两个字符串,即pattern和value。 pattern字符串由字母"a"和"b"组成,用于描述字符串中的模式。 例如,字符串"catcatgocatgo"匹配模式"aabab"(其中"cat"是"a&q…...
一天吃透SpringCloud面试八股文
1、什么是Spring Cloud ? Spring cloud 流应用程序启动器是基于 Spring Boot 的 Spring 集成应用程序,提供与外部系统的集成。Spring cloud Task,一个生命周期短暂的微服务框架,用于快速构建执行有限数据处理的应用程序。 Sprin…...
java生成图片缩略图
目录 前言一、使用Base64编码方式1、基本方法2、压缩本地图片保存到本地3、压缩网络图片到图片服务器 二、使用thumbnailator工具方式1、导入依赖2、压缩本地图片保存到本地 前言 下面介绍了两种获取图片缩略图的方式,全都不是一次性压缩,如果没有达到设…...
《统计学习方法》——隐马尔可夫模型(下)
学习算法 HMM的学习,在有观测序列的情况下,根据训练数据是否包含状态序列,可以分别由监督学习算法和无监督学习算法实现。 监督学习算法 监督学习算法就比较简单,基于已有的数据利用极大似然估计法来估计隐马尔可夫模型的参数。…...
Liunx top 命令详解
文章目录 top补充说明语法选项top交互命令实例 top 显示或管理执行中的程序 补充说明 top命令 可以实时动态地查看系统的整体运行情况,是一个综合了多方信息监测系统性能和运行信息的实用工具。通过top命令所提供的互动式界面,用热键可以管理。 语法…...
基于 SpringBoot 的医院固定资产系统
本文将介绍基于 SpringBoot 技术的医院固定资产系统的设计和实现。医院固定资产管理是医疗机构管理工作的重要组成部分,它对医院的正常运营和管理具有重要的意义。本系统的设计和实现将有助于医疗机构更好地管理和维护其固定资产。 1. 系统需求分析 医院固定资产管…...
【企业信息化】第2集 免费开源ERP: Odoo 16 销售管理系统
文章目录 前言一、概览二、使用功能1.通过清晰报价提高销售效率2.创建专业报价单3.管理订单及合同4.简化沟通5.维护产品&价格6.直观的报告7.集成 三、总结 前言 世界排名第一的免费开源ERP: Odoo 16 销售管理系统。通过Odoo Sign应用程序和在线支付,发送报价。…...
浅谈数据治理
大家好 ,近年来,数据治理成为挖掘数据价值的重要手段和工具。随着大数据平台和工业互联网兴起,数据治理平台主要采用数据中台技术和微服务架构初步替代传统架构,面向大数据架构下,为数据资源中心与外部数据系统提供数据…...
Matlab入门教程003|MATLAB变量|MATLAB命令
MATLAB变量 每个MATLAB变量可以是数组或者矩阵。 用一个简单的方法指定变量。例如: x 3 % defining x and initializing it with a value MATLAB执行上述语句,并返回以下结果: x 3 上述的例子创建了一个1-1的矩阵名为x和的值存储…...
【啃书C++Primer5】-编写一个简单C++程序
每个C程序都包含一个或多个函数(function),其中一个必须命名为main。操作系统通过调用main来运行C程序。下面是一个非常简单的main函数,它什么也不干,只是返回给操作系统一个值: int main() {return 0; }一个函数的定义包含四部分:返回类型(r…...
GoView 是一个Vue3搭建的低代码数据可视化开发平台
一、总览 开源、精美、便捷的「数据可视化」低代码开发平台 二、整体介绍 框架:基于 Vue3 框架编写,使用 hooks 写法抽离部分逻辑,使代码结构更加清晰; 类型:使用 TypeScript 进行类型约束,减少未知错误…...
【面试篇】Redis持久化面试题
文章目录 Redis持久化🙎♂️面试官:什么是Redis持久化? AOF日志AOF日志原理🙎♂️面试官:AOF日志是怎么工作的/AOF写入磁盘的流程?🙎♂️面试官: 刚刚说到了Redis先执行写入的…...
哈工大软件过程与工具作业2
云原生技术云原生技术 哈尔滨工业大学 计算机科学与技术学院/国家示范性软件学院 2022年秋季学期 《软件过程与工具》课程 作业报告 作业 2:需求分析UML建模 姓名 学号 联系方式 石卓凡 120L021011 944613709qq.com/18974330318 目 录 1 需求概述...........…...
SDN控制器三平面(软件定义网络、OOB)
目录 又名 三个独立的平面或层 SDN数据流 控制流量的带外(OOB) 优势 技术...
嘉兴桐乡会计考证实操-考初级会计真的有用吗?
一边说着:考初级会计门槛太低了,谁都能考;一边又争先恐后的去报考,考初级会计真的是有用的吗?为什么这么多人一边说考了没用却一直在努力备考呢? 关于这类的话题,其实一直都存在,但不…...
约翰霍普金斯大学诺奖得主涉嫌造假,撤回5篇PNAS论文
2019年,约翰霍普金斯大学的著名基因医学科学家Gregg L. Semenza博士因为“发现细胞如何感知和适应氧气供应”,和另外两名科学家( William Kaelin Jr. and Peter J. Ratcliffe)分享当年的生理医学诺贝尔奖。 近期,Gregg…...
React的表单数据绑定
当我们在页面中使用表单提交数据时,react是如何拿取表单数据的呢 这里通过两种方式来实现 非受控组件实现 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" conte…...
Dubbo——微服务框架(单体式->分布式->微服务)
是什么? Dubbo是阿里巴巴开源的基于Java的高性能RPC(一种远程调用)分布式服务框架,致力于提供高性能和透明化的RPC远程服务调用方案,以及SOA服务治理方案,它提供了三大核心能力:面向接口的远程…...
【Spring Cloud】Feign传递HttpServletRequest
这里我的业务场景是:在请求头中获取服务端登录时传给客户端的token,并且客户端将token放在请求头中。以至于我需要在参数传递上传入HttpServletRequest。如果你非要向我一样传入HttpServletRequest对象那么就往下看,当然你如果可以改成其他参…...
烟火识别智能监测系统 yolov5
烟火识别智能监测系统基于pythonyolov5网络模型算法智能分析技术,烟火识别智能监测算法模型对现场画面进行实时分析,发现现场出现烟火立即抓拍实时告警。我们选择当下卷积神经网络YOLOv5来进行火焰识别检测。6月9日,Ultralytics公司开源了YOL…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
