寒假冬令营（算法编程）1月13日（字符串）

1月13日（字符串）

题目描述（1）

459. 重复的子字符串

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• 1 <= s.length <= 104

• s 由小写英文字母组成

解题结果

Java

在这个解法中，使用了KMP算法的Next数组的思想。具体步骤如下：

1. 构建Next数组：通过遍历字符串构建Next数组，Next数组的值表示当前位置之前的字符串中最长的相同前缀和后缀的长度。

2. 判断条件：如果最后一个位置的Next数组值大于0且字符串长度能够整除（字符串长度 - 最后一个位置的Next数组值），则说明存在重复的子字符串。

这样，我们可以通过构建Next数组来判断字符串是否是由重复的子字符串构成的。

在Java中，字符比较使用charAt方法，数组的下标从0开始。这个解法在判断条件的选择上运用了KMP算法的核心思想。

class Solution {
 ?  public boolean repeatedSubstringPattern(String s) {
 ? ? ?  int n = s.length();
 ? ? ? ?
 ? ? ?  // 构建Next数组
 ? ? ?  int[] next = new int[n];
 ? ? ?  getNext(s, next);
 ? ? ? ?
 ? ? ?  // 如果满足条件，说明存在重复的子字符串
 ? ? ?  return next[n - 1] > 0 && n % (n - next[n - 1]) == 0;
 ?  }
 ? ?
 ?  private void getNext(String s, int[] next) {
 ? ? ?  int j = 0;
 ? ? ?  for (int i = 1; i < s.length(); i++) {
 ? ? ? ? ?  while (j > 0 && s.charAt(i) != s.charAt(j)) {
 ? ? ? ? ? ? ?  j = next[j - 1];
 ? ? ? ? ?  }
 ? ? ? ? ?  if (s.charAt(i) == s.charAt(j)) {
 ? ? ? ? ? ? ?  j++;
 ? ? ? ? ?  }
 ? ? ? ? ?  next[i] = j;
 ? ? ?  }
 ?  }
}

C语言

代码采用了类似于使用Java的KMP算法的解法。它包括了一个getNext函数来计算Next数组，而主要的repeatedSubstringPattern函数则根据Next数组的值判断条件。使用malloc为next数组分配内存，并使用free释放内存。

bool kmp(char* query, char* pattern) {
 ?  int n = strlen(query);
 ?  int m = strlen(pattern);
 ?  int fail[m];
 ?  memset(fail, -1, sizeof(fail));
 ?  for (int i = 1; i < m; ++i) {
 ? ? ?  int j = fail[i - 1];
 ? ? ?  while (j != -1 && pattern[j + 1] != pattern[i]) {
 ? ? ? ? ?  j = fail[j];
 ? ? ?  }
 ? ? ?  if (pattern[j + 1] == pattern[i]) {
 ? ? ? ? ?  fail[i] = j + 1;
 ? ? ?  }
 ?  }
 ?  int match = -1;
 ?  for (int i = 1; i < n - 1; ++i) {
 ? ? ?  while (match != -1 && pattern[match + 1] != query[i]) {
 ? ? ? ? ?  match = fail[match];
 ? ? ?  }
 ? ? ?  if (pattern[match + 1] == query[i]) {
 ? ? ? ? ?  ++match;
 ? ? ? ? ?  if (match == m - 1) {
 ? ? ? ? ? ? ?  return true;
 ? ? ? ? ?  }
 ? ? ?  }
 ?  }
 ?  return false;
}
?
bool repeatedSubstringPattern(char* s) {
 ?  int n = strlen(s);
 ?  char k[2 * n + 1];
 ?  k[0] = 0;
 ?  strcat(k, s);
 ?  strcat(k, s);
 ?  return kmp(k, s);
}

C++

在这个解法中，getNext 函数用于构建Next数组，而 repeatedSubstringPattern 函数则用于判断字符串是否由重复的子字符串构成。在 repeatedSubstringPattern 中，它使用了动态数组 std::vector 来存储Next数组。

这个解法的思路和前面提到的C和Java版本是一致的，它使用了KMP算法的思想，通过构建Next数组来判断字符串是否是由重复的子字符串构成的。

class Solution {
public:
 ?  bool repeatedSubstringPattern(std::string s) {
 ? ? ?  int n = s.length();
?
 ? ? ?  // 构建Next数组
 ? ? ?  std::vector<int> next(n, 0);
 ? ? ?  getNext(s, next);
?
 ? ? ?  // 如果满足条件，说明存在重复的子字符串
 ? ? ?  return next[n - 1] > 0 && n % (n - next[n - 1]) == 0;
 ?  }
?
private:
 ?  void getNext(const std::string& pattern, std::vector<int>& next) {
 ? ? ?  int len = pattern.length();
 ? ? ?  int j = 0;
?
 ? ? ?  for (int i = 1; i < len; i++) {
 ? ? ? ? ?  while (j > 0 && pattern[i] != pattern[j]) {
 ? ? ? ? ? ? ?  j = next[j - 1];
 ? ? ? ? ?  }
 ? ? ? ? ?  if (pattern[i] == pattern[j]) {
 ? ? ? ? ? ? ?  j++;
 ? ? ? ? ?  }
 ? ? ? ? ?  next[i] = j;
 ? ? ?  }
 ?  }
};

Python

KMP

class Solution:
 ?  def repeatedSubstringPattern(self, s: str) -> bool:
 ? ? ?  n = len(s)
?
 ? ? ?  # 构建Next数组
 ? ? ?  next_array = [0] * n
 ? ? ?  self.get_next(s, next_array)
?
 ? ? ?  # 如果满足条件，说明存在重复的子字符串
 ? ? ?  return next_array[-1] > 0 and n % (n - next_array[-1]) == 0
?
 ?  def get_next(self, pattern: str, next_array: list) -> None:
 ? ? ?  j = 0
?
 ? ? ?  for i in range(1, len(pattern)):
 ? ? ? ? ?  while j > 0 and pattern[i] != pattern[j]:
 ? ? ? ? ? ? ?  j = next_array[j - 1]
 ? ? ? ? ?  if pattern[i] == pattern[j]:
 ? ? ? ? ? ? ?  j += 1
 ? ? ? ? ?  next_array[i] = j

还可以使用一种简便而巧妙的方法来判断字符串 s 是否由重复的子字符串构成。下面是对这段代码的解释：

1. (s + s): 将字符串 s 与自身连接，形成一个长度为 2 * len(s) 的字符串。

2. [1:-1]: 切片操作，取出连接后的字符串的第2个字符到倒数第2个字符之间的子串。这是为了去掉连接后的字符串的首尾两个字符。

3. s in ...: 使用 in 操作符判断原始字符串 s 是否是连接后的字符串的子串。

整个代码的逻辑是，如果一个字符串是由重复的子字符串构成的，那么将这个字符串连接自身后去掉首尾字符，原始字符串仍然会是连接后的字符串的子串。因此，如果 s in (s + s)[1:-1] 为真，就说明 s 是由重复的子字符串构成的。

这种方法虽然简洁，但不是基于传统的字符串匹配算法（如KMP）的实现。这个方法的时间复杂度取决于字符串的长度和切片操作，通常是比较高效的。

class Solution:
 ?  def repeatedSubstringPattern(self, s: str) -> bool:
 ? ? ?  return s in (s + s)[1:-1]

题目描述（2）

242. 有效的字母异位词

. - 力扣（LeetCode）

给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。

注意：若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

• 1 <= s.length, t.length <= 5 * 104

• s 和 t 仅包含小写字母

相关知识点

哈希算法

解题结果

Java

class Solution {
 ?  public boolean isAnagram(String s, String t) {
 ? ? ?  // 如果两个字符串长度不相等，肯定不是字母异位词
 ? ? ?  if (s.length() != t.length()) {
 ? ? ? ? ?  return false;
 ? ? ?  }
?
 ? ? ?  // 使用数组记录每个字母的出现次数
 ? ? ?  int[] table = new int[26];
?
 ? ? ?  // 遍历字符串 s，统计每个字母出现的次数
 ? ? ?  for (int i = 0; i < s.length(); i++) {
 ? ? ? ? ?  table[s.charAt(i) - 'a']++;
 ? ? ?  }
?
 ? ? ?  // 遍历字符串 t，减少对应字母的出现次数
 ? ? ?  for (int i = 0; i < t.length(); i++) {
 ? ? ? ? ?  table[t.charAt(i) - 'a']--;
?
 ? ? ? ? ?  // 如果某个字母出现次数为负数，说明 t 中包含了 s 中不存在的字母，不是字母异位词
 ? ? ? ? ?  if (table[t.charAt(i) - 'a'] < 0) {
 ? ? ? ? ? ? ?  return false;
 ? ? ? ? ?  }
 ? ? ?  }
?
 ? ? ?  // 如果以上条件都没有触发，说明两个字符串是字母异位词
 ? ? ?  return true;
 ?  }
}

C语言

bool isAnagram(char* s, char* t) {
 ?  // 如果两个字符串长度不相等，肯定不是字母异位词
 ?  int len_s = 0, len_t = 0;
 ?  while (s[len_s] != '\0') {
 ? ? ?  len_s++;
 ?  }
 ?  while (t[len_t] != '\0') {
 ? ? ?  len_t++;
 ?  }
 ? ?
 ?  if (len_s != len_t) {
 ? ? ?  return false;
 ?  }
?
 ?  // 使用数组记录每个字母的出现次数
 ?  int table[26] = {0};
?
 ?  // 遍历字符串 s，统计每个字母出现的次数
 ?  for (int i = 0; i < len_s; i++) {
 ? ? ?  table[s[i] - 'a']++;
 ?  }
?
 ?  // 遍历字符串 t，减少对应字母的出现次数
 ?  for (int i = 0; i < len_t; i++) {
 ? ? ?  table[t[i] - 'a']--;
?
 ? ? ?  // 如果某个字母出现次数为负数，说明 t 中包含了 s 中不存在的字母，不是字母异位词
 ? ? ?  if (table[t[i] - 'a'] < 0) {
 ? ? ? ? ?  return false;
 ? ? ?  }
 ?  }
?
 ?  // 如果以上条件都没有触发，说明两个字符串是字母异位词
 ?  return true;
}

C++

class Solution {
public:
 ?  bool isAnagram(string s, string t) {
 ? ? ?  // 如果两个字符串长度不相等，肯定不是字母异位词
 ? ? ?  if (s.length() != t.length()) {
 ? ? ? ? ?  return false;
 ? ? ?  }
?
 ? ? ?  // 使用哈希表记录每个字母的出现次数
 ? ? ?  unordered_map<char, int> charCount;
?
 ? ? ?  // 遍历字符串 s，统计每个字母出现的次数
 ? ? ?  for (char c : s) {
 ? ? ? ? ?  charCount[c]++;
 ? ? ?  }
?
 ? ? ?  // 遍历字符串 t，减少对应字母的出现次数
 ? ? ?  for (char c : t) {
 ? ? ? ? ?  charCount[c]--;
?
 ? ? ? ? ?  // 如果某个字母出现次数为负数，说明 t 中包含了 s 中不存在的字母，不是字母异位词
 ? ? ? ? ?  if (charCount[c] < 0) {
 ? ? ? ? ? ? ?  return false;
 ? ? ? ? ?  }
 ? ? ?  }
?
 ? ? ?  // 如果以上条件都没有触发，说明两个字符串是字母异位词
 ? ? ?  return true;
 ?  }
};

Python

class Solution:
 ?  def isAnagram(self, s: str, t: str) -> bool:
 ? ? ?  # 如果两个字符串长度不相等，肯定不是字母异位词
 ? ? ?  if len(s) != len(t):
 ? ? ? ? ?  return False
?
 ? ? ?  # 使用字典记录每个字母的出现次数
 ? ? ?  char_count = {}
?
 ? ? ?  # 遍历字符串 s，统计每个字母出现的次数
 ? ? ?  for char in s:
 ? ? ? ? ?  char_count[char] = char_count.get(char, 0) + 1
?
 ? ? ?  # 遍历字符串 t，减少对应字母的出现次数
 ? ? ?  for char in t:
 ? ? ? ? ?  char_count[char] = char_count.get(char, 0) - 1
?
 ? ? ? ? ?  # 如果某个字母出现次数为负数，说明 t 中包含了 s 中不存在的字母，不是字母异位词
 ? ? ? ? ?  if char_count[char] < 0:
 ? ? ? ? ? ? ?  return False
?
 ? ? ?  # 如果以上条件都没有触发，说明两个字符串是字母异位词
 ? ? ?  return True