网站建设数据的需求分析,wordpress 压力,上海网站建设哪家专业,网站数据库空间大小28. 找出字符串中第一个匹配项的下标
题目链接#xff1a;28. 找出字符串中第一个匹配项的下标
思路1#xff1a;先来写一下暴力解法。
时间复杂度O(n*m)
class Solution {public int strStr(String haystack, String needle) {// 暴力解法先来一遍for (int i 0; i …28. 找出字符串中第一个匹配项的下标
题目链接28. 找出字符串中第一个匹配项的下标
思路1先来写一下暴力解法。
时间复杂度O(n*m)
class Solution {public int strStr(String haystack, String needle) {// 暴力解法先来一遍for (int i 0; i haystack.length(); i) {if (i needle.length() haystack.length()) return -1;boolean targ true;for (int j 0; j needle.length(); j) {if (needle.charAt(j) ! haystack.charAt(i j)) {targ false;}}if (targ) {return i;}}return -1;}
}思路2kmp。
算法原理通过前缀表即next数组来记录模式串与主串不匹配时模式串应当从那里开始重新匹配。重点在于求解前缀表即next数组。next数组每个位置的值就是从开始到当前位置的字符串的最长公共前缀最长相等前缀。一旦模式串与主串不匹配时next数组当前位置的前一个位置的元素就是模式串要回退到的位置。
实现方法先求解next数组分为四步 ① 初始化j指向前缀末尾位置i指向后缀末尾位置 ② 当前后缀不相同时前缀末尾进行回退 ③ 当前后缀相同时前缀末尾加一 ④ next数组赋值。 然后根据next数组完成模式串与主串的匹配。
时间复杂度O(nm)
class Solution {public int strStr(String haystack, String needle) {// kmp实现int[] next getNext(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 1 - needle.length();return i - j 1;}}return -1;}private int[] getNext(String s) {int[] next new int[s.length()];// 初始化j指向前缀末尾位置i指向后缀末尾位置int j 0;next[0] 0;for (int i 1; i next.length; i) {// 当前后缀不相同时前缀末尾进行回退while (j 0 s.charAt(i) ! s.charAt(j)) {j next[j - 1];}// 当前后缀相同时前缀末尾加一if (s.charAt(i) s.charAt(j)) {j;}// next数组赋值next[i] j;}return next;}
}思路3字符串哈希。相当于记模板了贴一下原博客链接。字符串哈希,帮您解决记不住kmp的烦恼~
