LeetCode刷题之旅（简单-10）：实现strStr()

LeetCode刷题之旅（简单-10）：实现strStr()

2019年5月20日

目录

​​题目：实现strStr()​​

​​解决方法1：暴力拆解字符串，逐个比较字符​​

​​性能结果：​​

​​小结：​​

​​解决方法2：调用字符串的substring切割方法​​

​​性能结果：​​

​​分析：​​

​​小结：​​

​​看下JDK源码：​​

​​解决方法3：暴力穷举法​​

​​性能结果：​​

​​分析：​​

​​解决方法4：KMP 算法​​

​​性能结果：​​

​​分析：​​

​​小结：​​

​​解决方法5：双指针方法​​

​​性能结果：​​

​​小结：​​

题目：实现strStr()

解决方法1：暴力拆解字符串，逐个比较字符

package leetCode;/** * Date: 2019/5/20 13 :22 */public class RealizeStrStr { public static void main(String[] args){// String haystack = "heallo";// String needle = "ll";// String haystack = "aaaaa";// String needle = "bba";// String haystack = "aaaaa";// String needle = ""; String haystack = "a"; String needle = "a"; int index = strStr(haystack, needle); System.out.println("index="+index); } public static int strStr(String haystack, String needle) { if ("".equals(needle)){ return 0; } if (needle == null || haystack == null || needle.length() > haystack.length()){ return -1; } // 1.两个字符串转为字符数组 char[] chars1 = haystack.toCharArray(); char[] chars2 = needle.toCharArray(); // 2.遍历第一个字符数组 for (int i=0;i

性能结果：

小结：

确实是最笨最暴力的方法了，考虑了元素越界的情况（needle字符串长度从匹配索引开始不可以越界）；时间复杂度：O((m−n)n)

解决方法2：调用字符串的substring切割方法

class Solution { public int strStr(String S, String T) { int n1 = S.length(); int n2 = T.length(); if (n1 < n2) return -1; else if ( n2 == 0) return 0; for (int i = 0; i < n1 - n2 + 1; i++ ){ if (S.substring(i, i+n2).equals(T)) return i; } return -1; }}

性能结果：

分析：

巧妙之处：调用库函数，String类的分割方法。

小结：

确实思路新奇，起码我一开始没想过；所以这个是要有一定JDK熟练度才行；但是我依然有一个疑问：使用 substring 方法，里面会有一个越界检测，当超出结束位置时，会抛出

StringIndexOutOfBoundsException

看下JDK源码：

public String substring(int beginIndex, int endIndex) { if (beginIndex < 0) { throw new StringIndexOutOfBoundsException(beginIndex); } if (endIndex > value.length) { throw new StringIndexOutOfBoundsException(endIndex); } int subLen = endIndex - beginIndex; if (subLen < 0) { throw new StringIndexOutOfBoundsException(subLen); } return ((beginIndex == 0) && (endIndex == value.length)) ? this : new String(value, beginIndex, subLen); }

解决方法3：暴力穷举法

class Solution { public int strStr(String S, String T) { if (T == null || T.length() == 0) return 0; int[] next = new int[T.length()]; getNext(T, next); int i = 0; int j = 0; while (i < S.length() && j < T.length()) { if (j == -1 || S.charAt(i) == T.charAt(j)) { i++; j++; } else j = next[j]; } if (j == T.length()) return i - j; return -1; } private void getNext(String t, int[] next) { next[0] = -1; int i = 0; int j = -1; while (i < t.length() - 1) { if (j == -1 || t.charAt(i) == t.charAt(j)) { i++; j++; next[i] = j; } else { j = next[j]; } } }}

性能结果：

分析：

从结果看，性能比我写的要弱一点；从代码看，一开始看的一头雾水；

解决方法4：KMP 算法

KMPclass Solution { public int strStr(String haystack, String needle) { int[][] dfa; int M = needle.length(); int R = 256; dfa = new int[R][M]; int N = haystack.length(); if( M==0){ return 0; } dfa[needle.charAt(0)][0]=1; for (int X=0,j=1;j

性能结果：

分析：

KMP算法，大跌眼镜，性能比不了一般的暴力法（这是因为比较两个字符串都很短，所以没有看出该算法的优越性）；优秀的算法，要看懂得多花时间；

小结：

KMP算法是一种改进的​​字符串匹配​​​算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为​​克努特​​​——​​莫里斯​​​——​​普拉特​​​操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。​​时间复杂度​​O(m+n)。​​Solution { public int strStr(String haystack, String needle) { char[] hayArr = haystack.toCharArray(); char[] needArr = needle.toCharArray(); int i = 0; //主串(haystack)的位置 int j = 0; //模式串(needle)的位置 while (i < hayArr.length && j < needArr.length) { if (hayArr[i] == needArr[j]) { // 当两个字符相等则比较下一个 i++; j++; } else { i = i - j + 1; // 一旦不匹配，i后退 j = 0; // j归零 } } if (j == needArr.length) { //说明完全匹配 return i - j; } else { return -1; } }}

性能结果：

小结：

设置两个指针i和j，分别用于指向主串(haystack)和模式串(needle)从左到右开始一个个字符匹配如果主串和模式串的两字符相等，则i和j同时后移比较下一个字符如果主串和模式串的两字符不相等，就跳回去，即模式串向右移动，同时模式串指针归零(i = 1; j = 0)；3.所有字符匹配结束后，如果模式串指针指到串尾(j = needle.length)，说明完全匹配，此时模式串出现的第一个第一个位置为：i - j

网友说是貌似类似“KMP”的一种解法..

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。