Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 3

Description

Find the Index of the First Occurrence in a String

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

Constraints:

• 1 <= haystack.length, needle.length <= 104
• haystack and needle consist of only lowercase English characters.

Solution

class KMP {
  vector<int> table{-1};
  string pattern;
  int patternLen;
public:
  KMP(string &pattern): pattern(pattern) {
    patternLen = pattern.length();
    table.resize(patternLen);
    int pos = 1;
    int cnd = 0;
    while(pos < patternLen) {
      if(pattern[pos] == pattern[cnd]) {
        table[pos] = table[cnd];
      } else {
        table[pos] = cnd;
        while(cnd >= 0 && pattern[pos] != pattern[cnd]) {
          cnd = table[cnd];
        }
      }
      pos += 1;
      cnd += 1;
    }
  }

  int search(const string &s) const {
    int posPattern = 0;
    int posStr = 0;
    int len = s.length();
    while(posStr < len) {
      if(s[posStr] == pattern[posPattern]) {
        posStr += 1;
        posPattern += 1;
        if(posPattern == patternLen) return posStr - patternLen;
      } else {
        posPattern = table[posPattern];
        if(posPattern < 0) {
          posPattern += 1;
          posStr += 1;
        }
      }
    }
    return -1;
  }
};

class Solution {
public:
  int strStr(string haystack, string needle) {
    if(needle.empty()) return 0;
    if(needle.length() > haystack.length()) return -1;
    return KMP(needle).search(haystack);
  }
};

// Accepted
// 79/79 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 29.81 % of cpp submissions (6.3 MB)