day09 | 字符串2 | 双指针法总结

0.引言

●28. 实现 strStr()
●459.重复的子字符串
●字符串总结
●双指针回顾

1.找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 10<sup>4</sup>
• haystack 和 needle 仅由小写英文字符组成

Discussion | Solution

1.1.自己想法及代码实现

• 暴力法走一波？

/*
 * @lc app=leetcode.cn id=28 lang=cpp
 *
 * [28] 找出字符串中第一个匹配项的下标
 */

// @lc code=start
class Solution {
 public:
  int strStr(string haystack, string needle) {
    if (needle.size() > haystack.size()) return -1;
    int idx1 = 0;
    while (idx1 <= haystack.size() - needle.size()) {
      if (str_contain_check(haystack, needle, idx1)) {
        return idx1;
      } else {
        idx1++;
      }
    }
    return -1;
  }

 private:
  bool str_contain_check(const std::string& str1, const std::string& str2,
                         int str1_idx) {
    if (str1.size() - str1_idx < str2.size()) return false;
    int str2_idx = 0;
    while (str2_idx < str2.size()) {
      if (str1[str1_idx] != str2[str2_idx]) {
        return false;
      }
      str1_idx++;
      str2_idx++;
    }
    return true;
  }
};
// @lc code=end

暴力解法竟然不会超时呀

image.png

1.2.参考思想及代码实现

KMP 算法

2.重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

• 1 <= s.length <= 10<sup>4</sup>
• s 由小写英文字母组成

Discussion | Solution

2.1.自己想法及代码实现

• 同样使用暴力法，碰了一鼻子灰：

/*
 * @lc app=leetcode.cn id=459 lang=cpp
 *
 * [459] 重复的子字符串
 */

// @lc code=start
class Solution {
 public:
  bool repeatedSubstringPattern(string s) {
    if (s.size() == 1) return false;
    // todo
    std::string substr = find_substr(s, 0);
    std::cout << "substr: " << substr;
    if (str_contain_repeat(s, substr)) {
      return true;
    }
    return false;
  }

 private:
  std::string find_substr(const string& str, uint8_t skip) {
    if (str.empty()) return "";
    int idx = 1;
    char cmp_char = str[0];
    uint8_t count_cmp_char = 0;
    while (idx < str.size()) {
      if (str[idx] == cmp_char) {
        if (count_cmp_char == skip) {
          return str.substr(0, idx);
        }
        count_cmp_char++;
      }
      idx++;
    }
    return "";
  }

  bool str_contain_repeat(const std::string& str1, const std::string& str2) {
    if (str1.size() % str2.size() != 0) return false;
    int times = 0, size_times = str1.size() / str2.size();
    while (times < size_times) {
      // 左闭右开
      int str2_idx = 0;
      while (str2_idx < str2.size()) {
        int str1_idx = times * str2.size() + str2_idx;
        if (str1[str1_idx] != str2[str2_idx])
          return false;
        else
          str2_idx++;
      }
      times++;
    }
    return true;
  }
};

image.png

这个test case本身就很魔幻。还是得KMP解题，毕竟这就是量身打造的题目。

2.2.参考思想及代码实现

挖坑！！

3.总结

• 字符串总结

• 双指针总结

周末需要再过一遍，自己再动手总结一下。