0.引言

●28. 實(shí)現(xiàn) strStr()
●459.重復(fù)的子字符串
●字符串總結(jié)
●雙指針回顧

1.找出字符串中第一個(gè)匹配項(xiàng)的下標(biāo)

給你兩個(gè)字符串 haystack 和 needle 派草，請(qǐng)你在 haystack 字符串中找出 needle 字符串的第一個(gè)匹配項(xiàng)的下標(biāo)（下標(biāo)從 0 開(kāi)始）抱既。如果 needle 不是 haystack 的一部分谚殊，則返回 -1腐晾。

示例 1：

輸入：haystack = "sadbutsad", needle = "sad"
輸出：0
解釋?zhuān)?sad" 在下標(biāo) 0 和 6 處匹配。
第一個(gè)匹配項(xiàng)的下標(biāo)是 0 呀洲，所以返回 0 舅柜。

示例 2：

輸入：haystack = "leetcode", needle = "leeto"
輸出：-1
解釋?zhuān)?leeto" 沒(méi)有在 "leetcode" 中出現(xiàn)，所以返回 -1 捺僻。

提示：

• 1 <= haystack.length, needle.length <= 10<sup>4</sup>
• haystack 和 needle 僅由小寫(xiě)英文字符組成

Discussion | Solution

1.1.自己想法及代碼實(shí)現(xiàn)

• 暴力法走一波？

/*
 * @lc app=leetcode.cn id=28 lang=cpp
 *
 * [28] 找出字符串中第一個(gè)匹配項(xiàng)的下標(biāo)
 */

// @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

暴力解法竟然不會(huì)超時(shí)呀

image.png

1.2.參考思想及代碼實(shí)現(xiàn)

KMP 算法

2.重復(fù)的子字符串

給定一個(gè)非空的字符串 s 崇裁，檢查是否可以通過(guò)由它的一個(gè)子串重復(fù)多次構(gòu)成匕坯。

示例 1:

輸入: s = "abab"
輸出: true
解釋: 可由子串 "ab" 重復(fù)兩次構(gòu)成。

示例 2:

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

示例 3:

輸入: s = "abcabcabcabc"
輸出: true
解釋: 可由子串 "abc" 重復(fù)四次構(gòu)成寇壳。 (或子串 "abcabc" 重復(fù)兩次構(gòu)成。)

提示：

• 1 <= s.length <= 10<sup>4</sup>
• s 由小寫(xiě)英文字母組成

Discussion | Solution

2.1.自己想法及代碼實(shí)現(xiàn)

• 同樣使用暴力法妻怎，碰了一鼻子灰：

/*
 * @lc app=leetcode.cn id=459 lang=cpp
 *
 * [459] 重復(fù)的子字符串
 */

// @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) {
      // 左閉右開(kāi)
      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

這個(gè)test case本身就很魔幻壳炎。還是得KMP解題，畢竟這就是量身打造的題目。

2.2.參考思想及代碼實(shí)現(xiàn)

挖坑Ｄ浔纭腰耙！

3.總結(jié)

• 字符串總結(jié)

• 雙指針總結(jié)

周末需要再過(guò)一遍，自己再動(dòng)手總結(jié)一下铲球。