首页 > 其他 > 详细

LeetCode Longest Substring Without Repeating Characters

时间:2014-03-16 03:09:43      阅读:409      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        if (len < 2) return len;
        char cnt[256];
        memset(cnt, 0, sizeof(cnt));
        
        const char* p = s.c_str();
        const char* q = p + 1;
        const char* end = s.c_str() + len - 1;
        
        int mlen = 1;
        cnt[*p] = 1;
        
        while(q <= end) {
            char ch = *q;
            int clen = q - p + (ch == 0);
            
            if (cnt[ch]) { // the character ch already exist in substr[p,q]
                for(; *p != ch; p++) cnt[*p] = 0;
                p++;
            } else {
                cnt[ch] = 1;
            }
            if (clen > mlen) mlen = clen;
            q++;
        }
        
        return mlen;
    }
};
bubuko.com,布布扣

用[p, q]表示一个子串,cnt[ch]表示在这个子串中字符ch出现的次数,如果q移动到一个新的位置发现该位置上的字符ch对应的cnt[ch]==1,说明字符ch已经在[p, q-1]的子串中出现过,那么符合要求的子串必然不会包括[p, q]因为已经有重复了,那么我们就要让移动到子串中与ch重复的那个字符后面的位置如r(移动的同时要把经过的字符对应的计数清零),那么[r, q]子串中就没有重复了,就又可以继续向后检测了。

LeetCode Longest Substring Without Repeating Characters,布布扣,bubuko.com

LeetCode Longest Substring Without Repeating Characters

原文:http://www.cnblogs.com/lailailai/p/3601875.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!