乘风破浪：LeetCode真题_028_Implement strStr()
一、前言
这次是字符串匹配问题，找到最开始匹配的位置，并返回。
二、Implement strStr()
2.1 问题
当模式串为空的时候，返回索引0，空字符串也是一个字符串。
2.2 分析与解决
注意到一些细节之后，我们首先想到了用笨办法来解决，其次又想到了KMP算法来匹配，需要求next数组。
笨办法比较：
class Solution {
public int strStr(String haystack, String needle) {
for(int i=0;i<= haystack.length()-needle.length();i++){
if(haystack.substring(i, i + needle.length() ).equals(needle)){
return i;
}
}
return -1;
}
}
KMP算法：
public class Solution {
/**
* 题目大意
* 实现实现strStr()函数，判断一个字符串在另一个字符串中出现的位置。如果不匹配就返回-1。
*
* 解题思路
* 使用KMP算法进行实现
*/
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null) {
return -1;
}
if (needle.length() > haystack.length()) {
return -1;
}
if ("".equals(haystack)) {
if ("".equals(needle)) {
return 0;
} else {
return -1;
}
} else {
if ("".equals(needle)) {
return 0;
}
}
return kmpIndex(haystack, needle);
}
private int kmpIndex(String haystack, String needle) {
int i = 0;
int j = 0;
int[] next = next(needle);
while (i < haystack.length() && j < needle.length()) {
if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
++i;
++j;
} else {
j = next[j];
}
}
if (j == needle.length()) {
return i - j;
} else {
return -1;
}
}
private int[] next(String needle) {
int[] next = new int[needle.length()];
next[0] = -1;
int i = 0;
int j = -1;
int k = needle.length() - 1;
while (i < k) {
if (j == -1 || needle.charAt(i) == needle.charAt(j)) {
++i;
++j;
if (needle.charAt(i) != needle.charAt(j)) {
next[i] = j;
} else {
next[i] = next[j];
}
} else {
j = next[j];
}
}
return next;
}
}
当然还有一种作弊的方法，那就是直接使用现有的方法库：
import java.lang.StringBuilder;
class Solution {
public int strStr(String haystack, String needle) { StringBuilder sb = new StringBuilder(haystack);
return sb.indexOf(needle);
}
}
三、总结
可以看到很多问题的细节非常多，其次解决问题的方法本质上来说也有优劣。对于KMP算法，我们一定要深刻的掌握，这样可以提升我们处理比较大量数据的字符串的能力。