Problem 3 : Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. 
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

这道题感觉上与kmp算法类似,而实际上暴力枚举会超时,所以还是静下来好好想想怎么优化代码。假设字符串为”abcdecfg”,在匹配到第二个’c’时出现重复,这时应该从’d’开始重新匹配,而不是’b’。

解法:

字符串长度为0则直接返回0;长度为1则直接返回1;设置头指针pre,尾指针loc;每次遍历[pre,loc-1]位置与loc位置比较字符是否有重复,若重复位置为flag,则pre=flag+1;否则loc++,同时判断当前子串长是否大于最大长度;loc走到最后一个位置时,要再做一次判断子串长度。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0)
            return 0;
        if (s.length() == 1)
            return 1;
        int max = 0, len = 0;// 保存字符串最长值和当前值
        int flag;// 判重返回值
        int pre = 0;// 起点位置
        int loc = 0;// 现在位置
        while (loc != s.length()) {
            flag = judge(pre, loc, s);
            if (flag == -1) {// 没有相同
                loc++;
            } else {// 有相同
                len = loc - pre;// 计算本次长度
                max = (max < len) ? len : max;
                pre = flag + 1;// 前指针后移
            }
        }
        len = loc - pre;// 最长串可能在最后
        max = (max < len) ? len : max;
        return max;
    }

    public int judge(int pre, int loc, String s) {
        int i;
        char now;
        char end = s.charAt(loc);
        for (i = pre; i < loc; i++) {
            now = s.charAt(i);
            if (now == end)
                return i;
        }
        return -1;
    }
}

发布者

VC-Robot

游戏爱好者,动漫迷,C++修炼中,编程菜鸟,随性

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.