Leetcode 实现strStr()

本文最后更新于:2020年11月19日 上午

地址:https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/5/strings/38/

题目

实现 strStr() 函数。

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

示例 1:

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

示例 2:

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

说明:

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

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

我的解决方案

class Solution {
public:
    int strStr(string haystack, string needle) {
        int addr;
        if (haystack.size() < needle.size())   //当haystack.size() < needle.size()时显然不存在满足条件的情况
            addr = -1;
        else {
            if (needle.size() == 0)   //当needle是空字符串时返回0
                addr = 0;
            else {     //当haystack.size() >= needle.size()时
                bool find = false;     //标记是否找到满足条件的情况
                for (int i = 0; i < haystack.size(); i++) {    //遍历字符串haystack查找与字符串needle首字符相同的位置
                    if (haystack[i] == needle[0]) {
                        bool isEqual = true;    //标记以下标i开始的长度为needle.size()的字符串是否与字符串needle相等
                        for (int j = i; j < i + needle.size(); j++) {
                            if (haystack[j] != needle[j - i]) {    //一旦某一位不相等说明以i开始的长度为needle.size()的字符串不满足条件
                                isEqual = false;
                                break;
                            }
                        }
                        if (isEqual == true) {    //说明以i开始的长度为needle.size()的字符串与字符串needle不相等
                            find = true;
                            addr = i;
                            break;
                        }
                    }
                    else continue;
                }
                if (find == false)    //没找到满足条件的情况,返回-1
                    addr = -1;
            }
        }
        return addr;
    }
};

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!