LEETCODE 1316. Distinct Echo Substrings 解题思路分析

题目大意：

不同的循环子字符串

给你一个字符串 text ，请你返回满足下述条件的 不同 非空子字符串的数目：

可以写成某个字符串与其自身相连接的形式。
例如，abcabc 就是 abc 和它自身连接形成的。

示例 1：

输入：text = "abcabcabc"
输出：3
解释：3 个子字符串分别为 "abcabc" ， "bcabca" 和 "cabcab" 

示例 2：

输入：text = "leetcodeleetcode"
输出：2
解释：2 个子字符串为 "ee" 和 "leetcodeleetcode" 。

提示：

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1316

解题思路分析：

这道题并没有想到太好的解题思路，尝试了一下暴力解，虽然效率不高，但是可以通过所有测试。

暴力解的大体思路为，2层循环，第一层循环是遍历每个子串的开头位置，第二层循环为该子串长度，如果当前子串与相邻的同长度子串相同，即可认定2子串组成的区间为一个结果。为了去除重复，我们使用Set类来保存所有找到的子串，循环结束后查看set的大小即是返回结果。

实现代码：

public int distinctEchoSubstrings(String text) {
    // 保存找到的不重复的循环子串
    HashSet<String> set = new HashSet<>();
    // 字符串长度
    int n = text.length();
    // 循环子串开头位置
    for (int i = 0; i < n; i++) {
        // 循环子串长度
        for(int j=0;(j+1)*2+i-1<n;j++){
            // 当前子串长度
            int length = j+1;
            // 当前子串
            String s1=text.substring(i,i+length);
            // 与当前子串长度相同的相邻子串
            String s2=text.substring(i+length, i+length*2);
            // 如果2子串相同，将其加入返回结果
            if(s1.equals(s2)) set.add(s1);
        }
    }
    return set.size();
}

本题解法执行时间为685ms。

Runtime: 685 ms, faster than 54.52% of Java online submissions for Distinct Echo Substrings.

Memory Usage: 40.8 MB, less than 100.00% of Java online submissions for Distinct Echo Substrings.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1316-distinct-echo-substrings-解题思路分析/