LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 这就是 std::string::find 的功能

class Solution {
 public:
  int strStr(string haystack, string needle) { return haystack.find(needle); }
};

• 其原理是朴素字符串匹配算法，检查以每个字符作为开始的子字符串是否能被匹配，对于长度为 n 的文本，长度为 m 的模式字符串，时间复杂度 O(mn)

class Solution {
 public:
  int strStr(string haystack, string needle) {
    if (empty(needle)) {
      return 0;
    }
    int m = size(haystack);
    int n = size(needle);
    for (int i = 0; i < m; ++i) {
      if (m - i < n) {
        break;
      }
      if (haystack[i] == needle[0]) {  // 检查是否匹配首元素
        int j = 0;
        while (haystack[i + j] == needle[j]) {  // 继续匹配其他位置
          ++j;
          if (j == n) {  // 匹配完整个 needle
            return i;    // 返回 haystack 当前下标
          }
        }
      }
    }
    return -1;
  }
};

• C++17 提供了 Boyer–Moore–Horspool 算法 和 Boyer–Moore 算法，对于长度为 n 的文本，长度为 m 的模式字符串，BMH 算法最优时间复杂度 O(n)，最差时间复杂度 O(mn)，BM 算法最优时间复杂度 O(n / m)，最差时间复杂度 O(mn)，BM 算法对于测试用例 n 个 a、n - 1 个 a 与 1 个 b 会超时

class Solution {
 public:
  int strStr(string haystack, string needle) {
    if (empty(haystack) && empty(needle)) {
      return 0;
    }
    auto it = search(begin(haystack), end(haystack),
                     boyer_moore_horspool_searcher{begin(needle), end(needle)});
    return it != end(haystack) ? it - begin(haystack) : -1;
  }
};

• 这里略过 BMH 和 BM 算法，介绍一种原理类似的字符串匹配算法 Knuth–Morris–Pratt 算法，KMP 算法时间复杂度为 O(m + n)

012345678901234  // 文本下标
bacbababaabcbab  // 文本 T
ababaca          // 模式字符串 P

// 开始匹配
012345678901234  // 文本下标
bacbababaabcbab  // T
ababaca          // P
↑
不匹配，由于 P 是首字符，下一步从 T 的下一位开始比较

012345678901234  // 文本下标
bacbababaabcbab  // T
 ababaca         // P
 ↑
 匹配，下一步比较 T 和 P 的下一位

012345678901234  // 文本下标
bacbababaabcbab  // T
 ababaca         // P
  ↑
  不匹配，回退到 P 的首字符

012345678901234  // 文本下标
bacbababaabcbab  // T
  ababaca        // P
  ↑
  不匹配，由于 P 是首字符，下一步从 T 的下一位开始比较

012345678901234  // 文本下标
bacbababaabcbab  // T
   ababaca       // P
   ↑
   不匹配，由于 P 是首字符，下一步从 T 的下一位开始比较

012345678901234  // 文本下标
bacbababaabcbab  // T
    ababaca      // P
    ↑
    匹配，下一步比较 T 和 P 的下一位

...

012345678901234  // 文本下标
bacbababaabcbab  // T
    ababaca      // P
        ↑
        匹配，下一步比较 T 和 P 的下一位

012345678901234  // 文本下标
bacbababaabcbab  // T
    ababaca      // P
         ↑
         不匹配

对于朴素匹配算法，下一步将回退到 T 的下一位

012345678901234  // 文本下标
bacbababaabcbab  // T
     ababaca     // P
     ↑

KMP 算法无需回退 T 的比较位置，仅回退 P 的比较位置

012345678901234  // 文本下标
bacbababaabcbab  // T
    ababaca      // P
         ↑
         不匹配

注意到，不匹配位置之前的字符串中，存在相同的最长前缀和后缀 aba
由于 P 不匹配位置之前的字符都与 T 匹配，而前缀与后缀相同
所以只需要回退到前缀的下一个位置
由于已经是最长前缀，因此回退到此位置肯定不会遗漏其它匹配的情况

012345678901234  // 文本下标
bacbababaabcbab  // T
    ..ababaca    // P
    - -  ↑
    ↑ ↑  不匹配

仍然不匹配，而不匹配位置之前的字符串中，存在相同的最长前缀和后缀 a
继续回退到前缀的下一个位置

012345678901234  // 文本下标
bacbababaabcbab  // T
      ..ababaca  // P
      - -↑
      ↑ ↑不匹配

此时不匹配位置之前没有相同的前缀和后缀，回退到 P 的首字符

012345678901234  // 文本下标
bacbababaabcbab  // T
         ababaca // P
         ↑

012345678901234  // 文本下标
bacbababaabcbab  // T
         ababaca // P
           ↑
           不匹配，之前没有相同的前缀和后缀，回退到 P 的首字符

012345678901234
bacbababaabcbab     // T
           ababaca  // P
           ↑
           不匹配，由于 P 是首字符，下一步从 T 的下一位开始比较

012345678901234
bacbababaabcbab
            ababaca
            ↑
            不匹配，由于 P 是首字符，下一步从 T 的下一位开始比较

012345678901234
bacbababaabcbab
             ababaca
             ↑
             匹配，下一步比较 T 和 P 的下一位

012345678901234
bacbababaabcbab
             ababaca
              ↑
              由于 T 已遍历结束，仍未匹配完 P，返回 -1

• KMP 算法的优化点在于，文本的比较指针不会左移，因此只需要遍历一遍文本即可。对于模式字符串，关键是找出回退位置，即匹配失败位置前的子串中，与后缀相同的最长前缀的长度，匹配失败时将模式字符串回退到该位置即可。为模式字符串构建一个数组作为 DFA，来表示模式匹配失败时要回退的位置，这个数组称为 next 数组，或者 pi 数组，pi[i] 表示第 i 个字符结尾的子串中，与后缀相同的最长前缀长度

1234567  // P[1] == 'a'
ababaca  // P
↑
pi[1] = 0  // 第 1 个字符，默认为 0

1234567  // P[1]P[2] == "ab"
ababaca  // P
 ↑
 pi[2] = 0  // ab 前缀为 a，后缀为 b，不相同

1234567  // P[1]...P[3] == "aba"
ababaca  // P
  ↑
  pi[3] = 1  // aba 有相同的前缀和后缀 a，长度为 1

1234567  // P[1]...P[4] == "abab"
ababaca  // P
   ↑
   pi[4] = 2  // abab 有相同的前缀和后缀 ab，长度为 2

1234567  // P[1]...P[5] == "ababa"
ababaca  // P
    ↑
    pi[5] = 3  // ababa 有相同的前缀和后缀 aba，长度为 3

1234567  // P[1]...P[6] == "ababac"
ababaca  // P
     ↑
     pi[6] = 0  // ababac 没有相同的前缀和后缀

1234567  // P[1]...P[7] == "ababaca"
ababaca  // P
      ↑
      pi[7] = 1  // ababaca 有相同的前缀和后缀 a，长度为 1

i  1234567
P  ababaca
pi 0012301

• 对任意文本进行匹配时都可以用到这个数组

// 开始匹配
012345678901234  // 文本下标
bacbababaabcbab  // T
ababaca          // P
↑
T[0] != P[0]

012345678901234  // 文本下标
bacbababaabcbab  // T
 ababaca         // P
 ↑
 T[1] == P[0]

012345678901234  // 文本下标
bacbababaabcbab  // T
 ababaca         // P
  ↑
  T[2] != P[1]

pi[1] = 0，回退到 P[0]

012345678901234  // 文本下标
bacbababaabcbab  // T
  ababaca        // P
  ↑
  T[2] != P[0]

012345678901234  // 文本下标
bacbababaabcbab  // T
   ababaca       // P
   ↑
   T[3] != P[0]

012345678901234  // 文本下标
bacbababaabcbab  // T
    ababaca      // P
    ↑
    T[4] == P[0]

T[5] == P[1]
T[6] == P[2]
T[7] == P[3]

012345678901234  // 文本下标
bacbababaabcbab  // T
    ababaca      // P
        ↑
        T[8] == P[4]

012345678901234  // 文本下标
bacbababaabcbab  // T
    ababaca      // P
         ↑
         T[9] != P[5]

pi[5] = 3，回退到 P[3]

012345678901234  // 文本下标
bacbababaabcbab  // T
      ababaca    // P
         ↑
         T[9] != P[3]

pi[3] = 1，回退到 P[1]

012345678901234  // 文本下标
bacbababaabcbab  // T
        ababaca  // P
         ↑
         T[9] != P[1]

pi[1] = 0，回退到 P[0]

012345678901234  // 文本下标
bacbababaabcbab  // T
         ababaca // P
         ↑
         T[9] == P[0]

012345678901234  // 文本下标
bacbababaabcbab  // T
         ababaca // P
          ↑
          T[10] == P[1]

012345678901234  // 文本下标
bacbababaabcbab  // T
         ababaca // P
           ↑
           T[11] != P[2]

pi[2] = 0，回退到 P[0]

012345678901234
bacbababaabcbab
           ababaca
           ↑
           T[11] != P[0]

012345678901234
bacbababaabcbab
            ababaca
            ↑
            T[12] != P[0]

012345678901234
bacbababaabcbab
             ababaca
             ↑
             T[13] == P[0]

012345678901234
bacbababaabcbab
             ababaca
              ↑
              T[14] == P[1]，T 遍历结束，未匹配完 P，返回 -1

• 实际编程中，下标一般从 0 开始，pi 数组的构建算法如下

// i  0123456
// P  ababaca
// pi 0012301

vector<int> generate_pi(const string& pattern) {
  vector<int> pi(size(pattern));
  for (int i = 1, j = 0; i < size(pi); ++i) {
    // pattern[i] 为后缀尾字符，因此初始值为 1
    // pattern[j] 为前缀尾字符，因此初始值为 0
    while (j > 0 && pattern[i] != pattern[j]) {
      j = pi[j - 1];  // 前后缀尾字符不匹配，回退前缀直到与后缀相同或 j 为 0
    }
    if (pattern[i] == pattern[j]) {
      ++j;
    }
    pi[i] = j;
  }
  return pi;
}

• KMP 算法如下

class Solution {
 public:
  int strStr(string haystack, string needle) {
    if (empty(needle)) {
      return 0;
    }
    //  构建 pi 数组
    vector<int> pi(size(needle));
    for (int i = 1, j = 0; i < size(pi); ++i) {
      while (j > 0 && needle[i] != needle[j]) {
        j = pi[j - 1];
      }
      if (needle[i] == needle[j]) {
        ++j;
      }
      pi[i] = j;
    }
    //  遍历文本串
    for (int i = 0, j = 0; i < size(haystack); ++i) {
      while (j > 0 && haystack[i] != needle[j]) {
        j = pi[j - 1];  // 由于 pi 下标从 0 开始，回退到 pi[j - 1]
      }
      if (haystack[i] == needle[j]) {
        ++j;
      }
      if (j == size(needle)) {
        return i - size(needle) + 1;
      }
    }
    return -1;
  }
};

• std::strstr 提供了类似功能，strstr 源自 C 语言，复杂度由 C 标准库的实现决定

class Solution {
 public:
  int strStr(string haystack, string needle) {
    const char* pos = strstr(haystack.c_str(), needle.c_str());
    if (!pos) {
      return -1;
    }
    return pos - haystack.c_str();
  }
};