算法练习(3)-寻找最大的不重复子串

2021-05-04 10:30

阅读：687

标签：etc 开头最大 return 重复 sub 缓冲 move bst

要求：给定1个字符串，比如ababc，要求找出“第1个最长的不重复子串”，即："abc"

思路：遍历每个字符，寻找以它开头的不重复子串，遍历过程中，可以用一个Set作为缓冲区，存放曾经处理过的起始字符串。

过程：

(a)babc -> 子串为a

(ab)abc -> 子串为ab

(ab)abc -> 发现重复字符a，准备从第2个字符开始新一轮查找

a(b)abc -> 子串为b

a(ba)bc -> 子串为ba

a(ba)bc -> 发现重复字符b，准备第第3个字符开始新一轮查找

ab(a)bc -> 子串为a

ab(ab)c -> 子串为ab

ab(abc) -> 查找结束

代码：

    /**
     * 查找最长不重复子串
     *
     * @param s
     * @return
     */

    public String getFirstLongestSubstring(String s) {
        System.out.println(s);
        char[] arr = s.toCharArray();
        Set set = new HashSet();
        int right = -1, maxLen = -1;
        String subStr = "";
        for (int i = 0; i  0) {
                //缩小左边界
                set.remove(arr[i - 1]);
            }
            while (right + 1  maxLen) {
                maxLen = len;
                char[] temp = new char[maxLen];
                s.getChars(i, right + 1, temp, 0);
                subStr = new String(temp);
            }
            if (maxLen >= arr.length - i) {
                break;
            }
        }
        return subStr;
    }

算法练习(3)-寻找最大的不重复子串

标签：etc 开头最大 return 重复 sub 缓冲 move bst

原文地址：https://www.cnblogs.com/yjmyzz/p/13195620.html

上一篇：Python --- Python的简介

下一篇：python之文件的读取与写入

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：算法练习(3)-寻找最大的不重复子串
文章链接：http://soscw.com/index.php/essay/82230.html

亲，登录后才可以留言！

算法练习(3)-寻找最大的不重复子串

评论

热门文章

推荐文章

最新文章

置顶文章