LeetCode每日一题--StrStr()

昨天和朋友劳(da)逸(you)结(xi)合的时候，朋友告诉我他实现了一个Strstr()。然后我去看了一下，题目难度属于Easy。想着做出来还是简单的，于是立马动手操作了一把。

题目描述

实现 strStr() 函数。

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

示例 1:

输入: haystack = “hello”, needle = “ll”
输出: 2
示例 2:

输入: haystack = “aaaaa”, needle = “bba”
输出: -1

^{链接：https://leetcode-cn.com/problems/implement-strstr}. 来源：力扣（LeetCode） ↩

因为我是一个java党，我拿到这个题目一看，这不就是indexOf吗，于是我优雅的写下了第一行代码。。。。

1
2
3

public int strStr(String haystack, String needle) {
    return haystack.indexOf(needle);
}

临界情况

但是题目的本意显然不是让我们之间调用API，strStr()是C++的API，题目的本意是让我们实现他，短暂思索一下。我就开始了我接下来的思路。
既然要返回初始下标，那我直接将字符串转为char[]，通过判断数组下标，返回起始位置,当needle是空串的时候按照API的返回结果默认应该返回0，因此加了一层特殊的条件判断。然后开始思考indexOf如何实现。。

public int strStr(String haystack, String needle) {
    if (needle.length() == 0)
        return 0;
    char[] sources = haystack.toCharArray();
    char[] targets = needle.toCharArray();
    return indexOf(sources, targets, 0);
}

我们先来思考临界条件。当targets的长度大于sources长度的时候。那肯定是匹配不上的。因此直接返回-1。

private int indexOf(char[] sources, char[] targets, int fromIndex) {
    if (targets.length > sources.length)
        return -1;
}

处理思路

当满足targets的长度小于等于sources的长度的时候，我需要去寻找targets中第一个元素作为sources第一次出现的位置。如果从头至尾我都找不到这个元素，那么说明匹配不是，直接返回-1，如果我能找到这个元素的下标，则看后面能否完全匹配，若能这个第一次出现的位置就是返回下标。如果后面不完全匹配，那么我可以截取sources中这个下标到sources.length生成一个新的数组，我定义为newsources，重复这个匹配逻辑，如果匹配上，那么返回坐标就是sources中第一次出现的位置加上newsources中第一次出现的位置，如果没匹配上，就重复分割数组，直至匹配成功或者出现上面临界情况。

    class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0)
            return 0;
        char[] sources = haystack.toCharArray();
        char[] targets = needle.toCharArray();
        return indexOf(sources, targets, 0);
    }

    private int indexOf(char[] sources, char[] targets, int fromIndex) {
        if (targets.length > sources.length)
            return -1;
        //先找到第一个位置
        char Item = targets[0];
        BREAK:
        for (int i = 0; i < sources.length; i++) {
            if (sources[i] == Item) {
                fromIndex = i; //预设定
                for (int j = 0; j < targets.length; j++) {
                    if (i != 0 && i == sources.length - 1) {
                    //这里其实可以优化，当找到第一个位置之后，
                    //直接判断sources剩余长度是不是大于等于targets长度可省略很多次if判断
                        return -1; 
                    }
                    if (sources[i++] != targets[j]) {
                        fromIndex++;
                        break BREAK;
                    }
                }
                return fromIndex;
            }
            //全部遍历都找不到第一个元素，返回-1
            if (i + 1 == sources.length)
                return -1;
        }
        //递归
        int thenIndex = indexOf(Arrays.copyOfRange(sources, fromIndex, sources.length), targets, fromIndex);
        return thenIndex == -1 ? -1 : fromIndex + thenIndex;
    }
}

上面在遍历匹配的时候，我加了一层判断，因为可能sources剩余长度如果小于targets长度，i++之后 sources[i++]有可能会数组越界。这种处理其实不好，可以直接在遍历targets之前判断sources.length-fromIndex是不是比targets.length大。这样可以省略很多次if判断，

if(sources.length-fromIndex<targets.length){
    return -1;
}
for (int j = 0; j < targets.length; j++) {
    // if (i != 0 && i == sources.length - 1) {
    // //这里其实可以优化，当找到第一个位置之后，
    // //直接判断sources剩余长度是不是大于等于targets长度可省略很多次if判断
    //     return -1; 
    // }
    if (sources[i++] != targets[j]) {
        fromIndex++;
        break BREAK;
    }
}

其实类似字符串的匹配算法还有很多，比较有名的KMP算法，或者利用哈希表来处理，都是一些解决方案，仅此记录一下我的解法，勿喷勿喷。

...

00:00

LeetCode每日一题--StrStr()

leetCode算法系列

题目描述

临界情况

处理思路

...

标签

其他常用