leetcode:实现strStr()

发表于 分类于 阅读次数：

题目内容

实现 strStr() 函数。

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

示例

示例 1:

输入: haystack = “hello”, needle = “ll”

输出: 2

示例 2:

输入: haystack = “aaaaa”, needle = “bba”

输出: -1

类似C语言的 strstr() 以及 Java的 indexOf()函数。

python解法1

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        for i in range(len(haystack)-len(needle)+1):
            if(haystack[i:len(needle)+i])==needle:
                return i
        return -1

重点在于循环范围是两个字符串的差值。

java解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int strStr(String haystack, String needle) {
	    if(needle.equals("")){
	        return 0;
	    }
	    if(haystack.equals("")){
	        return -1;
	    }
		for(int i=0;i<=haystack.length();i++){< span>
	        if(i+needle.length()>haystack.length())
			{
	            return -1;
	        }
	        if(haystack.substring(i,i+needle.length()).equals(needle)){
	            return i;
	        }
	    }
	    return -1;
    }
}

该解法类似于python解法1，不过java要比python多出一些边界条件的限制，i+len(needle)与len(haystack）要进行比较，否则substring要报异常。

java解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int strStr(String haystack, String needle) {
	    if(needle.equals("")){
	            return 0;
	        }
	    if(haystack.equals("")){
	            return -1;
	        }
	    if (haystack.equals(needle)){
	            return 0;
	        }
	    int j=0;
		int i;	
	    for(i=0;i < haystack.length();i++){
	        if (j==needle.length()){
	            return i-j;
	        } 
	        if(haystack.charAt(i)==needle.charAt(j)){
	            ++j;
	        }else{
	            i-=j;
	            j=0;
	        }
	    }
	     if (j==needle.length()){
	            return i-j;
	        }
	    return -1;
    }
}

注意：
存在这样一个测试用例：

1
2
"mississippi"
"issip"

之所以在else语句里要加i=i-j，是因为需要考虑到之前有部分匹配的情况，需要将i返回到起初的下一位置。

0%