题目大意:给定两个字符串,求其中一个在另一个中第一次出现的位置。

题目描述

Implement strStr().

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

算法描述

本题需要做的是模拟一个字符串查找的函数,简单的做法即将子串与母串的每一位进行比较。

高级一点的做法可以使用KMP算法,但在本题中似乎不需要。

代码

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        
        for (int i = 0; i < n - m + 1; ++i) {
            bool flag = true;
            for (int j = 0; j < m; ++j) // 从母串的第i位开始与子串进行比较
                if (haystack[i + j] != needle[j]) {
                    flag = false;
                    break;
                }
            if (flag) return i;
        }
        return -1;
    }
};

登录发表评论 注册

反馈意见