首页 > 其他 > 详细

【编程】leetcode_longest substring without repeating characters

时间:2014-12-31 16:03:38      阅读:276      评论:0      收藏:0      [点我收藏+]
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        char cHash[256];
        int cnt = 0, maxCnt = 0;
        int i, j, k, sSz = s.size();
        char chRep;

        memset(cHash, 0, 256);

        cnt = 1;    // initialization        

        for(i = 0, cHash[0] = 0; i < sSz; )
        {
            cHash[s[i]] = 1;
            for (j = i + 1; j < sSz; j++)
            {
                if (cHash[s[j]] == 0)
                {
                    cnt++;        // increase length
                    cHash[s[j]] = 1;
                }
                else
                {
                    chRep = s[j];
                    break;    // got the same character
                }
            }

            if (cnt > maxCnt)    // renew the maxcnt
            {
                maxCnt = cnt;
            }

            // got the next i index, find where is the chSame
            for (k = j - cnt; k < j; k++)
            {
                if (s[k] == chRep)
                {
                    break;
                }
                cnt--;                // decrease
                cHash[s[k]] = 0;    // delete from hashtable
            }

            i = j;    // i start from the j position
        }

        return maxCnt;
    }
};

思路:

1. 使用char cHash[256]作为hash表来存储某个字符是否已经出现过;

2. 遍历字符串,出现的字符串在hash表中置1;

3. 一旦发现重复出现的字符串,返回当前子串查找,当前子串中在出现字符之前的字符从hash表中删除;

4. 下次循环可以接着子循环的位置继续下去,看上去是两层循环,其实对于整个字符串只会遍历一次。

【编程】leetcode_longest substring without repeating characters

原文:http://www.cnblogs.com/visong/p/4195795.html

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