代码随想录算法训练营二十四期第九天|LeetCode28. 找出字符串中第一个匹配项的下标、LeetCode459. 重复的子字符串

本文主要是介绍代码随想录算法训练营二十四期第九天|LeetCode28. 找出字符串中第一个匹配项的下标、LeetCode459. 重复的子字符串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、LeetCode28. 找出字符串中第一个匹配项的下标

题目链接:28. 找出字符串中第一个匹配项的下标
解法一:
我们可以用双重for循环去一次比较第一个字符串的子串与第二个字符串。时间复杂度是O(n^2)
代码如下:

class Solution {public int strStr(String haystack, String needle) {for(int i = 0; i <= haystack.length() - needle.length(); i++) {if(haystack.charAt(i) == needle.charAt(0)) {int j = i;for(int k = 0; k < needle.length(); k++) {if(haystack.charAt(j++) != needle.charAt(k)) {break;}else if(k == needle.length() - 1) {return i;}}}}return -1;}
}

解法二(KMP算法):
先通过模式串创建前缀表,(1、初始化;2、处理前后缀不想同情况;3、处理前后缀相同情况);
根据前缀表去寻找主串中是否有模式串。
代码如下:

class Solution {int[] getNext(int[] next, String s) {//创建前缀表int j = 0;next[0] = j;for(int i = 1; i < s.length(); i++) {while(j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];if(s.charAt(i) == s.charAt(j)) j++;next[i] = j;}return next;}public int strStr(String haystack, String needle) {int[] next = new int[needle.length()];next = getNext(next, needle);int j = 0;for(int i = 0; i < haystack.length(); i++) {while(j > 0 && haystack.charAt(i) != needle.charAt(j)) j = next[j - 1];if(haystack.charAt(i) == needle.charAt(j)) j++;if(j == needle.length()) return i - j + 1;}return -1;}
}

时间复杂度O(n)

二、LeetCode459. 重复的子字符串

题目链接:459. 重复的子字符串
KMP算法:
创建前缀表,求出最长想通前后缀长度len,如果len大于0并且(s.length() % (s.length()-len)==0),说明该字符串可以由一些长度为s.length() - len的子串重复构成。
具体分析请看卡哥的PPT解析

class Solution {int[] getNext(int[] next, String s) {int j = 0;next[0] = 0;for(int i = 1; i < s.length(); i++) {while(j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];if(s.charAt(i) == s.charAt(j)) j++;next[i] = j;}return next;}public boolean repeatedSubstringPattern(String s) {int[] next = new int[s.length()];next = getNext(next, s);if(next[s.length() - 1] > 0 &&s.length() % (s.length() - next[s.length() - 1]) == 0) return true;return false;}
}

时间复杂度O(n),空间复杂度O(n)

总结

初步了解KMP算法

这篇关于代码随想录算法训练营二十四期第九天|LeetCode28. 找出字符串中第一个匹配项的下标、LeetCode459. 重复的子字符串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/243921

相关文章

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一:使用GROUP BY和HAVING子句方法二:仅返回重复值方法三:返回完整记录方法四:

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

XML重复查询一条Sql语句的解决方法

《XML重复查询一条Sql语句的解决方法》文章分析了XML重复查询与日志失效问题,指出因DTO缺少@Data注解导致日志无法格式化、空指针风险及参数穿透,进而引发性能灾难,解决方案为在Controll... 目录一、核心问题:从SQL重复执行到日志失效二、根因剖析:DTO断裂引发的级联故障三、解决方案:修复

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码