leetcode [#28]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Implement strStr().

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

---

解决方案

public class Solution {
    public int strStr(String haystack, String needle) {
        int result = -1;
        int lenHaystack = haystack.length();
        int lenHayNeedle = needle.length();
        if(lenHayNeedle > lenHaystack) return -1;
        if(lenHayNeedle == 0) return 0;
        char[] str = haystack.toCharArray();
        char[] sub = needle.toCharArray();

        for(int n = 0; n < lenHaystack - lenHayNeedle + 1; n++){
            boolean flag = false;
            int num = 0;
            for(int m = 0; m < lenHayNeedle; m++){
                if(str[m + n] == sub[m]){
                    num++;
                    if(num == lenHayNeedle){
                        result = n;
                        flag = true;
                        break;
                    }
                }
            }
            if(flag){
                break;
            }
        }
        return result;
    }
}

---

注意事项

1. 实现查询子字符串开始位置下标的方法，在java中即indexOf()，当然不能直接使用这个方法。
2. 将两个字符串均转化成字符数组。
3. 对父字符串只需要遍历0~lenHaystack - lenHayNeedle这一段，因为如果包含子字符串，那么开始下标一定位于这一段。
4. 内层遍历子字符串，和父字符串当前段逐一比较即可。