Hard

题目描述

返回文本中能够写成某个字符串与其自身连接形式的不同非空子串的数量（即可以写成 a + a 的形式，其中 a 是某个字符串）。

示例 1：

输入：text = "abcabcabc"
输出：3
解释：这 3 个子串是 "abcabc"、"bcabca" 和 "cabcab"。

示例 2：

输入：text = "leetcodeleetcode"
输出：2
解释：这 2 个子串是 "ee" 和 "leetcodeleetcode"。

提示：

  • 1 <= text.length <= 2000
  • text 只包含小写英文字母

提示：

  • 给定文本的一个子串，如何检查它是否可以写成字符串与其自身的连接？
  • 我们可以在线性时间内完成，更快的方法是使用哈希。
  • 尝试所有子串并使用哈希来检查它们。

解题思路

这道题要求找出所有能够表示为 “a + a” 形式的不同子串，即由两个相同字符串拼接而成的子串。

核心思路：

  1. 暴力枚举：遍历所有可能的子串，检查是否满足条件
  2. 回文检查优化：对于长度为偶数的子串，检查前一半是否等于后一半
  3. 哈希优化：使用滚动哈希来快速比较两个字符串是否相等

具体步骤：

  1. 枚举所有起始位置 i
  2. 枚举所有结束位置 j，确保子串长度为偶数
  3. 对于每个偶数长度的子串，检查前一半和后一半是否相等
  4. 使用集合存储满足条件的子串，自动去重

时间复杂度优化思考：

  • 方法一：直接字符串比较，时间复杂度 O(n³)
  • 方法二：使用滚动哈希，时间复杂度 O(n²)

由于题目数据规模不大（n ≤ 2000），直接的字符串比较方法已经足够高效。滚动哈希虽然理论上更快，但实现复杂度较高，且在小数据规模下优势不明显。

推荐使用简洁的字符串切片比较方法，代码清晰易懂且效率满足要求。

代码实现

class Solution {
public:
    int distinctEchoSubstrings(string text) {
        set<string> result;
        int n = text.length();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j += 2) {
                int len = j - i + 1;
                if (len % 2 == 0) {
                    string substr = text.substr(i, len);
                    string left = substr.substr(0, len / 2);
                    string right = substr.substr(len / 2);
                    if (left == right) {
                        result.insert(substr);
                    }
                }
            }
        }
        
        return result.size();
    }
};

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        result = set()
        n = len(text)
        
        for i in range(n):
            for j in range(i + 1, n, 2):
                length = j - i + 1
                if length % 2 == 0:
                    substr = text[i:j + 1]
                    mid = length // 2
                    left = substr[:mid]
                    right = substr[mid:]
                    if left == right:
                        result.add(substr)
        
        return len(result)

public class Solution {
    public int DistinctEchoSubstrings(string text) {
        HashSet<string> result = new HashSet<string>();
        int n = text.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j += 2) {
                int length = j - i + 1;
                if (length % 2 == 0) {
                    string substr = text.Substring(i, length);
                    string left = substr.Substring(0, length / 2);
                    string right = substr.Substring(length / 2);
                    if (left == right) {
                        result.Add(substr);
                    }
                }
            }
        }
        
        return result.Count;
    }
}

var distinctEchoSubstrings = function(text) {
    const seen = new Set();
    const n = text.length;
    
    for (let i = 0; i < n; i++) {
        for (let len = 2; len <= n - i; len += 2) {
            const substr = text.substring(i, i + len);
            const half = len / 2;
            const left = substr.substring(0, half);
            const right = substr.substring(half);
            
            if (left === right) {
                seen.add(substr);
            }
        }
    }
    
    return seen.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n³)外层两重循环 O(n²)，字符串比较 O(n)
空间复杂度O(n²)存储所有可能的回文子串，最坏情况下有 O(n²) 个

相关题目