查找字符串中的第一个匹配项
最编程
2024-03-16 08:24:02
...
28.找出字符串中第一个匹配项
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle
字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。示例 1:
输入:haystack = “sadbutsad”, needle = “sad” 输出:0 解释:“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。 示例 2:输入:haystack = “leetcode”, needle = “leeto” 输出:-1 解释:“leeto” 没有在
“leetcode” 中出现,所以返回 -1 。提示:
1 <= haystack.length, needle.length <= 104 haystack 和 needle
仅由小写英文字符组成
思路 一
朴素匹配
顾名思义最简单的匹配方式但是时间复杂度较高
首先将字符串通过toCharArray
函数转为数组
for循环定义 i 指针指向hayStack数组的起始位置,索引在 [0 ~ (n - m + 1)]内遍历
嵌套while循环 如果字符匹配则 a ,b 指针继续同时向前
直到b = m或者 指针指向的内容不相同
最后返回 i 指针
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length();
int m = needle.length();
//字符串转成数组
char[] hay = haystack.toCharArray();
char[] ned = needle.toCharArray();
for (int i = 0; i <= n - m; i++){
int a = i, b = 0;
while (b < m && hay[a] == ned[b]){
++a;
++b;
}
//如果能够完全匹配。返回原串的发起点下标
if(b == m) return i;
}
return -1;
}
}
思路二
KMP算法
没啥好说的,写原理的帖子很多
当模版背下来就好
class Solution {
//KMP算法,源串为 string, 匹配串为pattern
//不管何时,string的指针不回溯
//pattern的指针有条件地回溯
public int strStr(String haystack, String needle) {
if (needle.length() == 0) return 0;
int[] next = new int[needle.length()];
getNext(next, needle);
int j = 0;
for (int i = 0; i < haystack.length(); i++) {
while (j > 0 && needle.charAt(j) != haystack.charAt(i))
//j指针回溯
j = next[j - 1];
if (needle.charAt(j) == haystack.charAt(i))
j++;
if (j == needle.length())
return i - needle.length() + 1;
}
return -1;
}
//寻找nxet数组
private void getNext(int[] next, String s) {
int j = 0;
next[0] = 0;
for (int i = 1; i < s.length(); i++) {
while (j > 0 && s.charAt(j) != s.charAt(i))
//如果 s.charAt(j) 和 s.charAt(i) 不相等,说明当前位置匹配失败,需要回溯到前一个可能匹配的位置,即 j = next[j - 1]。
j = next[j - 1];
//如果 s.charAt(j) 和 s.charAt(i) 相等,说明找到了一个更长的重复前缀和后缀,将 j 的值增加 1。
if (s.charAt(j) == s.charAt(i))
j++;
//将 j 的最新值赋给 next[i],表示在位置 i 处的字符之前的最长重复前缀和后缀的长度。
next[i] = j;
}
}
}
NEXT数组演示
推荐阅读
-
查找字符串中的第一个匹配项
-
438.查找字符串中的所有字母反义词
-
leetcode-438. 查找字符串中的所有字母反义词(滑动窗口)
-
查找字符串中的所有字母反义词
-
查找字符串中的所有字母反义词
-
稀疏从零开始算法注释 Day12-LeetCode:查找字符串中第一个匹配项的下标
-
Java 类加载器的作用 - 简介:类加载器是 Java™ 中一个非常重要的概念。类加载器负责将 Java 类的字节码加载到 Java 虚拟机中。本文首先详细介绍了 Java 类加载器的基本概念,包括代理模型、加载类的具体过程和线程上下文类加载器等。然后介绍了如何开发自己的类加载器,最后介绍了类加载器在 Web 容器和 OSGi™ 中的应用。 类加载器是 Java 语言的一项创新,也是 Java 语言广受欢迎的重要原因之一。它允许将 Java 类动态加载到 Java 虚拟机中并执行。类加载器从 JDK 1.0 开始出现,最初是为了满足 Java Applets 的需求而开发的,Java Applets 需要从远程位置下载 Java 类文件并在浏览器中执行。现在,类加载器已广泛应用于网络容器和 OSGi。一般来说,Java 应用程序的开发人员不需要直接与类加载器交互;Java 虚拟机的默认行为足以应对大多数情况。但是,如果遇到需要与类加载器交互的情况,而您又不太了解类加载器的机制,就很容易花费大量时间调试异常,如 ClassNotFoundException 和 NoClassDefFoundError。本文将详细介绍 Java 的类加载器,帮助读者深入理解 Java 语言中的这一重要概念。下面先介绍一些基本概念。 类加载器的基本概念 顾名思义,类加载器用于将 Java 类加载到 Java 虚拟机中。一般来说,Java 虚拟机以如下方式使用 Java 类:Java 源程序(.java 文件)经 Java 编译器编译后转换为 Java 字节代码(.class 文件)。类加载器负责读取 Java 字节代码并将其转换为 java.lang 实例。每个实例都用来表示一个 Java 类。通过该实例的 newInstance 方法创建该类的对象。实际情况可能更加复杂,例如,Java 字节代码可能是由工具动态生成或通过网络下载的。 基本上,所有类加载器都是 java.lang.ClassLoader 类的实例。下面将详细介绍这个 Java 类。 java.lang.ClassLoader 类简介 java.lang.ClassLoader 类的基本职责是根据给定类的名称为其查找或生成相应的字节码,然后根据这些字节码定义一个 Java 类,即 java.lang.Class 类的实例。除此之外,ClassLoader 还负责加载 Java 应用程序所需的资源,如图像文件和配置文件。不过,本文只讨论它加载类的功能。为了履行加载类的职责,ClassLoader 提供了许多方法,其中比较重要的方法如表 1 所示。下文将详细介绍这些方法。 表 1.与加载类相关的 ClassLoader 方法
-
乐码热门话题 100_查找字符串中的所有字母反义词
-
南邮OJ Web任务大揭秘:层层挑战剖析 1. 挑战一:迷宫般的目录探索 题目作者似乎穷举了所有可能的目录组合,最终在404.php中的