X

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-解题思路分析/
Categories: leetcode
kwantong: