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

《程序员面试金典(第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. 模式匹配(暴力破解 + 剪枝)

题目描述 你有两个字符串&#xff0c;即pattern和value。 pattern字符串由字母"a"和"b"组成&#xff0c;用于描述字符串中的模式。 例如&#xff0c;字符串"catcatgocatgo"匹配模式"aabab"&#xff08;其中"cat"是"a&q…...

一天吃透SpringCloud面试八股文

1、什么是Spring Cloud &#xff1f; Spring cloud 流应用程序启动器是基于 Spring Boot 的 Spring 集成应用程序&#xff0c;提供与外部系统的集成。Spring cloud Task&#xff0c;一个生命周期短暂的微服务框架&#xff0c;用于快速构建执行有限数据处理的应用程序。 Sprin…...

java生成图片缩略图

目录 前言一、使用Base64编码方式1、基本方法2、压缩本地图片保存到本地3、压缩网络图片到图片服务器 二、使用thumbnailator工具方式1、导入依赖2、压缩本地图片保存到本地 前言 下面介绍了两种获取图片缩略图的方式&#xff0c;全都不是一次性压缩&#xff0c;如果没有达到设…...

《统计学习方法》——隐马尔可夫模型(下)

学习算法 HMM的学习&#xff0c;在有观测序列的情况下&#xff0c;根据训练数据是否包含状态序列&#xff0c;可以分别由监督学习算法和无监督学习算法实现。 监督学习算法 监督学习算法就比较简单&#xff0c;基于已有的数据利用极大似然估计法来估计隐马尔可夫模型的参数。…...

Liunx top 命令详解

文章目录 top补充说明语法选项top交互命令实例 top 显示或管理执行中的程序 补充说明 top命令 可以实时动态地查看系统的整体运行情况&#xff0c;是一个综合了多方信息监测系统性能和运行信息的实用工具。通过top命令所提供的互动式界面&#xff0c;用热键可以管理。 语法…...

基于 SpringBoot 的医院固定资产系统

本文将介绍基于 SpringBoot 技术的医院固定资产系统的设计和实现。医院固定资产管理是医疗机构管理工作的重要组成部分&#xff0c;它对医院的正常运营和管理具有重要的意义。本系统的设计和实现将有助于医疗机构更好地管理和维护其固定资产。 1. 系统需求分析 医院固定资产管…...

【企业信息化】第2集 免费开源ERP: Odoo 16 销售管理系统

文章目录 前言一、概览二、使用功能1.通过清晰报价提高销售效率2.创建专业报价单3.管理订单及合同4.简化沟通5.维护产品&价格6.直观的报告7.集成 三、总结 前言 世界排名第一的免费开源ERP: Odoo 16 销售管理系统。通过Odoo Sign应用程序和在线支付&#xff0c;发送报价。…...

浅谈数据治理

大家好 &#xff0c;近年来&#xff0c;数据治理成为挖掘数据价值的重要手段和工具。随着大数据平台和工业互联网兴起&#xff0c;数据治理平台主要采用数据中台技术和微服务架构初步替代传统架构&#xff0c;面向大数据架构下&#xff0c;为数据资源中心与外部数据系统提供数据…...

Matlab入门教程003|MATLAB变量|MATLAB命令

MATLAB变量 每个MATLAB变量可以是数组或者矩阵。 用一个简单的方法指定变量。例如&#xff1a; x 3 % defining x and initializing it with a value MATLAB执行上述语句&#xff0c;并返回以下结果&#xff1a; x 3 上述的例子创建了一个1-1的矩阵名为x和的值存储…...

【啃书C++Primer5】-编写一个简单C++程序

每个C程序都包含一个或多个函数(function)&#xff0c;其中一个必须命名为main。操作系统通过调用main来运行C程序。下面是一个非常简单的main函数&#xff0c;它什么也不干&#xff0c;只是返回给操作系统一个值: int main() {return 0; }一个函数的定义包含四部分:返回类型(r…...

GoView 是一个Vue3搭建的低代码数据可视化开发平台

一、总览 开源、精美、便捷的「数据可视化」低代码开发平台 二、整体介绍 框架&#xff1a;基于 Vue3 框架编写&#xff0c;使用 hooks 写法抽离部分逻辑&#xff0c;使代码结构更加清晰&#xff1b; 类型&#xff1a;使用 TypeScript 进行类型约束&#xff0c;减少未知错误…...

【面试篇】Redis持久化面试题

文章目录 Redis持久化&#x1f64e;‍♂️面试官&#xff1a;什么是Redis持久化&#xff1f; AOF日志AOF日志原理&#x1f64e;‍♂️面试官&#xff1a;AOF日志是怎么工作的/AOF写入磁盘的流程&#xff1f;&#x1f64e;‍♂️面试官&#xff1a; 刚刚说到了Redis先执行写入的…...

哈工大软件过程与工具作业2

云原生技术云原生技术 哈尔滨工业大学 计算机科学与技术学院/国家示范性软件学院 2022年秋季学期 《软件过程与工具》课程 作业报告 作业 2&#xff1a;需求分析UML建模 姓名 学号 联系方式 石卓凡 120L021011 944613709qq.com/18974330318 目 录 1 需求概述...........…...

SDN控制器三平面(软件定义网络、OOB)

目录 又名 三个独立的平面或层 SDN数据流 控制流量的带外(OOB) 优势 技术...

嘉兴桐乡会计考证实操-考初级会计真的有用吗?

一边说着&#xff1a;考初级会计门槛太低了&#xff0c;谁都能考&#xff1b;一边又争先恐后的去报考&#xff0c;考初级会计真的是有用的吗&#xff1f;为什么这么多人一边说考了没用却一直在努力备考呢&#xff1f; 关于这类的话题&#xff0c;其实一直都存在&#xff0c;但不…...

约翰霍普金斯大学诺奖得主涉嫌造假,撤回5篇PNAS论文

2019年&#xff0c;约翰霍普金斯大学的著名基因医学科学家Gregg L. Semenza博士因为“发现细胞如何感知和适应氧气供应”&#xff0c;和另外两名科学家&#xff08; William Kaelin Jr. and Peter J. Ratcliffe&#xff09;分享当年的生理医学诺贝尔奖。 近期&#xff0c;Gregg…...

React的表单数据绑定

当我们在页面中使用表单提交数据时,react是如何拿取表单数据的呢 这里通过两种方式来实现 非受控组件实现 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" conte…...

Dubbo——微服务框架(单体式->分布式->微服务)

是什么&#xff1f; Dubbo是阿里巴巴开源的基于Java的高性能RPC&#xff08;一种远程调用&#xff09;分布式服务框架&#xff0c;致力于提供高性能和透明化的RPC远程服务调用方案&#xff0c;以及SOA服务治理方案&#xff0c;它提供了三大核心能力&#xff1a;面向接口的远程…...

【Spring Cloud】Feign传递HttpServletRequest

这里我的业务场景是&#xff1a;在请求头中获取服务端登录时传给客户端的token&#xff0c;并且客户端将token放在请求头中。以至于我需要在参数传递上传入HttpServletRequest。如果你非要向我一样传入HttpServletRequest对象那么就往下看&#xff0c;当然你如果可以改成其他参…...

烟火识别智能监测系统 yolov5

烟火识别智能监测系统基于pythonyolov5网络模型算法智能分析技术&#xff0c;烟火识别智能监测算法模型对现场画面进行实时分析&#xff0c;发现现场出现烟火立即抓拍实时告警。我们选择当下卷积神经网络YOLOv5来进行火焰识别检测。6月9日&#xff0c;Ultralytics公司开源了YOL…...

DM V5.0.6.03.103 Windows 2000 (2026.04.14)

...

【电子通识】为什么PCB能短接还要用0Ω电阻?0欧电阻怎么做降额?

简介 市面上有一种电阻叫0Ω电阻&#xff0c;又称跨接电阻&#xff0c;是一种标称阻值为0的特殊电阻。有没有想过&#xff0c;用PCB直接就可以实现短接变成0Ω的功能&#xff0c;那为什么还需要焊接一个0Ω电阻呢&#xff1f; 0Ω电阻是一种特殊用途的电阻&#xff0c;与常规贴…...

Local SDXL-Turbo实操手册:从键盘输入到画面生成的完整链路

Local SDXL-Turbo实操手册&#xff1a;从键盘输入到画面生成的完整链路 1. 什么是Local SDXL-Turbo&#xff1f; Local SDXL-Turbo是一个基于StabilityAI SDXL-Turbo构建的实时绘画工具。与传统的AI绘画工具需要等待几分钟生成不同&#xff0c;这个工具实现了真正的"打字…...

如何快速构建电商库存扫描系统:QuaggaJS条形码识别终极指南

如何快速构建电商库存扫描系统&#xff1a;QuaggaJS条形码识别终极指南 【免费下载链接】quaggaJS An advanced barcode-scanner written in JavaScript 项目地址: https://gitcode.com/gh_mirrors/qu/quaggaJS 在电商运营中&#xff0c;高效的库存管理是提升效率和降低…...

【AIAgent社会影响白皮书】:SITS2026首席专家独家解码3大颠覆性冲击与5年治理路线图

第一章&#xff1a;SITS2026专家&#xff1a;AIAgent的社会影响 2026奇点智能技术大会(https://ml-summit.org) AIAgent已从实验室原型演进为嵌入城市治理、医疗决策与教育服务的常态化社会基础设施。在SITS2026大会上&#xff0c;来自全球17个国家的跨学科专家共同指出&…...

02阶段:大模型部署机器人项目

一、ollama私有大模型本地部署 1.智聊机器人概述 ① 知道什么是聊天机器人 能够听懂人话&#xff0c;并且说出人话的程序。 1&#xff09;基本定义&#xff1a;一个用来模拟人类对话或聊天的程序。 2&#xff09;主要应用&#xff1a;客服支持、智能助手、社交互动、教育学习…...

GO-FLY国际化与多语言支持:面向全球用户的客服系统

GO-FLY国际化与多语言支持&#xff1a;面向全球用户的客服系统 【免费下载链接】goflylivechat 开源在线客服系统GO语言开发GO-FLY,免费在线客服系统/GOFLY LIVE CHAT: open source self-hosted private cloud customer support live chat software by golang 项目地址: http…...

“无穷套娃素数生成公式”框架下,孪生素数猜想已被证明【乖乖数学】

“无穷套娃素数生成公式”框架下&#xff0c;孪生素数猜想已被证明。 作者&#xff1a;乖乖数学 核心论证如下&#xff1a; 完备性定理 首先&#xff0c;系统已严格证明&#xff1a;对任意 k &#xff0c;区间 (C_k, C_{k1}) 内的所有奇数均为奇素数。 关键引理&#xff1a…...

终极指南:如何使用Python实现百度网盘直链解析与高速下载

终极指南&#xff1a;如何使用Python实现百度网盘直链解析与高速下载 【免费下载链接】baidu-wangpan-parse 获取百度网盘分享文件的下载地址 项目地址: https://gitcode.com/gh_mirrors/ba/baidu-wangpan-parse 你是否厌倦了百度网盘缓慢的下载速度&#xff1f;是否对会…...

跨模型、跨Agent、跨时序的追踪难题全解析,深度解读分布式因果推断追踪协议v2.1

第一章&#xff1a;AIAgent架构全链路追踪方案 2026奇点智能技术大会(https://ml-summit.org) AI Agent系统具备多阶段决策、工具调用、记忆检索与外部服务协同等复杂行为特征&#xff0c;传统基于HTTP请求的链路追踪&#xff08;如OpenTracing&#xff09;难以准确刻画其内部…...