【LeetCode】459. 重复的子字符串(KMP2.0)

2023-12-21 23:20

本文主要是介绍【LeetCode】459. 重复的子字符串(KMP2.0),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  今日学习的文章链接和视频链接

leetcode题目地址:459. 重复的子字符串

 代码随想录题解地址:代码随想录

题目简介

给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。

看到题目的第一想法(可以贴代码)

1. 记录每一个子串(从0开始,由短到长递增),一一与原字符串进行比较。

        好繁琐,写了好久,主要是没想清楚用哪种数据结构,引发了很多小bug。

        最后写了一个最暴力的解法(利用String类的substring)。。实在想赶紧写出来。

public boolean repeatedSubstringPattern(String s) {String res = "";int end = 1;int len = s.length();boolean check = true;while (end < len ){res = s.substring(0, end);int rLen = res.length();for (int com = 0; com < len; com = com + rLen){if (com+rLen <= len){if (!s.substring(com, com+rLen).equals(res)) {check = false;break;}}else return false;}if(check) return true;else check = true;end++;}return false;
}

实现过程中遇到哪些困难

1. 主要是没想清楚用哪种数据结构,引发了很多小bug。

看完代码随想录之后的想法

【解题思路】1. 暴力解法;2.移动匹配;3.KMP解法(s+s - 最长 相等 前后缀)

【想法】牛

看完视频自己写的ACC:

// 使用库函数(代替KMP算法部分)
public boolean repeatedSubstringPattern(String s) {String res = s + s;res = res.substring(1, res.length()-1);if(res.indexOf(s) == -1) return false;return true;
}
// 完全套用KMP算法(未简化)
public void getNext(int[] next, String s){int j = -1;next[0] = j;for (int i = 1; i < s.length(); i++){while(j >= 0 && s.charAt(i) != s.charAt(j+1)) j = next[j];if (s.charAt(i) == s.charAt(j+1)) j++;next[i] = j;}
}
public boolean repeatedSubstringPattern(String s) {String res = s + s;res = res.substring(1, res.length()-1);int[] next = new int[s.length()];getNext(next, s);int j = -1;for (int i = 0; i < res.length(); i++){while(j >= 0 && res.charAt(i) != s.charAt(j+1)) j = next[j];if (res.charAt(i) == s.charAt(j+1)) j++;if (j == s.length()-1) return true;}return false;
}

视频标答:

// KMP算法灵活应用
public void getNext(int[] next, String s){int j = -1;next[0] = j;for (int i = 1; i < s.length(); i++){while(j >= 0 && s.charAt(i) != s.charAt(j+1)) j = next[j];if (s.charAt(i) == s.charAt(j+1)) j++;next[i] = j;}
}
public boolean repeatedSubstringPattern(String s) {int len = s.length();if (len <= 1) return false;int[] next = new int[len];getNext(next, s);if (next[len - 1] >= 0 && len % (len-(next[len - 1]+1)) == 0) return true;return false;
}

学习时长


今日收获

1. 更熟悉了KMP算法的应用(先编辑next()数组,再将字串与原串进行比较)。

2. int[]数组排序:        Arrays.sort(intarr);

利用stream获取int[]的最大/小值:        int max/min = Arrays.stream(intarr).max().getAsInt();

打印int[]数组:        System.out.print(Arrays.toString(intarr));

这篇关于【LeetCode】459. 重复的子字符串(KMP2.0)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下:1. 字符串的不可变性:每次修改都创建新对象2. 使用 == 比较字符串,陷阱满

IDEA编译报错“java: 常量字符串过长”的原因及解决方法

《IDEA编译报错“java:常量字符串过长”的原因及解决方法》今天在开发过程中,由于尝试将一个文件的Base64字符串设置为常量,结果导致IDEA编译的时候出现了如下报错java:常量字符串过长,... 目录一、问题描述二、问题原因2.1 理论角度2.2 源码角度三、解决方案解决方案①:StringBui

C#从XmlDocument提取完整字符串的方法

《C#从XmlDocument提取完整字符串的方法》文章介绍了两种生成格式化XML字符串的方法,方法一使用`XmlDocument`的`OuterXml`属性,但输出的XML字符串不带格式,可读性差,... 方法1:通过XMLDocument的OuterXml属性,见XmlDocument类该方法获得的xm

Redis 多规则限流和防重复提交方案实现小结

《Redis多规则限流和防重复提交方案实现小结》本文主要介绍了Redis多规则限流和防重复提交方案实现小结,包括使用String结构和Zset结构来记录用户IP的访问次数,具有一定的参考价值,感兴趣... 目录一:使用 String 结构记录固定时间段内某用户 IP 访问某接口的次数二:使用 Zset 进行

Spring Boot 整合 ShedLock 处理定时任务重复执行的问题小结

《SpringBoot整合ShedLock处理定时任务重复执行的问题小结》ShedLock是解决分布式系统中定时任务重复执行问题的Java库,通过在数据库中加锁,确保只有一个节点在指定时间执行... 目录前言什么是 ShedLock?ShedLock 的工作原理:定时任务重复执行China编程的问题使用 Shed

JSON字符串转成java的Map对象详细步骤

《JSON字符串转成java的Map对象详细步骤》:本文主要介绍如何将JSON字符串转换为Java对象的步骤,包括定义Element类、使用Jackson库解析JSON和添加依赖,文中通过代码介绍... 目录步骤 1: 定义 Element 类步骤 2: 使用 Jackson 库解析 jsON步骤 3: 添

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

Oracle数据库使用 listagg去重删除重复数据的方法汇总

《Oracle数据库使用listagg去重删除重复数据的方法汇总》文章介绍了在Oracle数据库中使用LISTAGG和XMLAGG函数进行字符串聚合并去重的方法,包括去重聚合、使用XML解析和CLO... 目录案例表第一种:使用wm_concat() + distinct去重聚合第二种:使用listagg,

python修改字符串值的三种方法

《python修改字符串值的三种方法》本文主要介绍了python修改字符串值的三种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录第一种方法:第二种方法:第三种方法:在python中,字符串对象是不可变类型,所以我们没办法直接

MySQL中删除重复数据SQL的三种写法

《MySQL中删除重复数据SQL的三种写法》:本文主要介绍MySQL中删除重复数据SQL的三种写法,文中通过代码示例讲解的非常详细,对大家的学习或工作有一定的帮助,需要的朋友可以参考下... 目录方法一:使用 left join + 子查询删除重复数据(推荐)方法二:创建临时表(需分多步执行,逻辑清晰,但会