signed

QiShunwang

“诚信为本、客户至上”

【icyle】Leetcode-cn:28. 实现 strStr()

2021/3/21 11:00:47   来源:

题目

解答1:KMP算法(未AC,难度有点高)

思路

度娘找!

代码
时间复杂度和空间复杂度

解答2:Sunday算法

思路

请参考Test 的解答:Sunday算法,详细准确。(当很多解答比较晦涩难懂的情况下,我才会用自己的大白话说一遍)

代码

此处参考了上面解答中用户KeviN的C++实现。感谢。

/*
 * @lc app=leetcode.cn id=28 lang=cpp
 *
 * [28] 实现 strStr()
 */

// @lc code=start
#include <string>
#include <unordered_map>
using namespace std;
class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        int hlength = haystack.size();
        int nlength = needle.size();
        unordered_map<char, int> shift_table;
        // 建立模式串的偏移表
        //规则: 模式串中该字母出现的最右位置到尾部的距离+1
        for (int i = 0; i < nlength; i++)
        {
            shift_table[needle[i]] = nlength - i;
        }

        //进行匹配
        int i = 0;
        while (i <= hlength - nlength)
        {
            //从位置i开始nlength的长度,如果匹配模式串,则结束
            if (haystack.substr(i, nlength) == needle)
                return i;

            else
            {
                //模式串中存在该字符,则按照偏移值偏移
                if (shift_table.find(haystack[i + nlength]) != shift_table.end())
                {
                    i += shift_table[haystack[i + nlength]];
                }
                //否则直接跳过一个模式串的长度
                else
                {
                    i += nlength + 1;
                }
            }
        }
        return -1;
    }
};
// @lc code=end
时间复杂度和空间复杂度
  • 时间复杂度: O(mn) 。其中m是模式串的长度,n 是待匹配字符串的长度。最坏的情况下,除了必要的遍历待匹配字符串,也需要遍历一次模式串。
  • 空间复杂度:O(m) 。其中m是模式串的长度。定义了一个map作为偏移表使用。

反思与总结

Sunday算法真好用!KMP整整坐了一天都没做出来。。。