leetcode 28 Implement strStr()
z
 2017-12-22 17:02:48  

28. Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

1
2
3
Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

1
2
3
Input: haystack = "aaaaa", needle = "bba"
Output: -1

第一反应就是建立一个hashMap<String, Integer> 来存储substring和对应的index。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int strStr(String haystack, String needle) {
        // 注意当要查找的string为“”时，返回的是0，不是-1
      	if(needle.length() == 0){
            return 0;
        }
        
        int window = needle.length();
        HashMap<String, Integer> m = new HashMap<String, Integer>();
        for (int i=0;i<=haystack.length()-window; i++){// 这里注意是<=，因为有可能两个字符串长度相等
            String substring = haystack.substring(i,i+window);
            m.put(substring, i);
            if(m.containsKey(needle)){// 返回首个index，所以这里的判断语句要在for之内
                return m.get(needle);
            }
        }
        return -1;
    }
}

but，在discuss区看到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int strStr(String haystack, String needle) {
        int l1 = haystack.length(), l2 = needle.length();
        if (l1 < l2) {
            return -1;
        } else if (l2 == 0) {
            return 0;
        }
        int threshold = l1 - l2;
        for (int i = 0; i <= threshold; ++i) {
       		// 直接判断是否相等就好，不用hashMap！！！！
            if (haystack.substring(i,i+l2).equals(needle)) {
                return i;
            }
        }
        return -1;
    }
}