实现strStr()

2018-06-12

实现strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

1 2	输入: haystack = "hello", needle = "ll" 输出: 2

示例 2:

1 2	输入: haystack = "aaaaa", needle = "bba" 输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf()) 定义相符。

思路：一开始决定利用contains()函数来做，后来发现contains函数只能返回包含或者不包含的结果，并不能返回匹配的位置，所以索性就自己写一个吧。整体思路也不难，首先分情况讨论：

1.needle为空，则按题目要求，返回0即可；

2.needle的长度大于haystack的长度，肯定不能匹配，返回-1；

3.needle的长度小于或者等于haystack的长度。

　　第3种情况最复杂，首先这种情况下，最先要考虑的是在haystack中找到和needle的首字符匹配的第一个位置，利用一个while循环即可，设置索引，记录下第一个匹配的位置h，之后再将needle中的下一个字符和haystack中的第h+1个字符相比较，如果直到needle走完全部自己的字符，haystack也全部匹配且未越界，则返回h即可。如果没有全部匹配（即needle字符串没有走到最后），需要考虑haystack后面是不是还有重复的子串可以匹配（比如haystack=”mississippi”,而needle=”issip”的场景中），而不能简单的返回-1。为了验证后面的haystack后面的子串是否能匹配，只需要截取haystack中h+1到haystack.length()的子串再递归调用strStr()即可。

java代码如下：

public class StrStr {
	  public static int strStr(String haystack, String needle) {
	        if(needle.length()==0){
	            return 0;
	        }
	        
	        int nlength=needle.length();
	        int hlength=haystack.length();
	        //如果needle长度大于haystack长度，则肯定不匹配
	        if(nlength>hlength) {
	        	return -1;
	        }
	        if(nlength==1 && hlength==1 && needle==haystack) {
	        	return 0;
	        }
	        int n=0;
	        int h=0;
	        //在haystack中找到第一个和needle中首字符匹配的位置。
	        while(haystack.charAt(h)!=needle.charAt(n)){
	            h++;
	            if(h==hlength) {
	            	return -1;
	            }
	        }
	        int k=h;
	        if(h<=hlength-nlength){
	            while(haystack.charAt(h)==needle.charAt(n)){
	                h++;
	                n++;
	                if(n==nlength) {
	                	break;
	                }
	            }
	            if(h<=hlength && n==nlength){
	                return k;
	            }else {
	            	/**
	            	 * 此时不匹配，但是不能保证haystack后面不会再出现匹配的字符串，所以从k+1到haystack字符串的末尾截取新的字符串。
	            	 * 递归调用匹配算法，当后面的子串可以匹配needle且匹配位置为子串的c时,在原串中的位置就为k+c+1。
	            	 */
	            	String nhaystack=new String(haystack.substring(k+1, hlength));
	            	int c=strStr(nhaystack,needle);
	            	if(c!=-1) {
	            		return k+c+1;
	            	}
	            }
	        }
	        return -1;
	    }
	  public static void main(String[] args) {
		String s1="mississippi";
		String s2="issip";
		System.out.println(strStr(s1, s2));
	}
}