[leetcode题解]03.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.


给定一个字符串,找出不含有重复字符的最长子串的长度。

示例:

给定 “abcabcbb” ,没有重复字符的最长子串是 “abc” ,那么长度就是3。

给定 “bbbbb” ,最长的子串就是 “b” ,长度是1。

给定 “pwwkew” ,最长子串是 “wke” ,长度是3。请注意答案必须是一个子串,”pwke” 是 子序列  而不是子串。

这个题目主要是思路要正确,题目意思很简单明了,这个时候我们就要考虑,找当前位置往前不含重复字符的长度,首先找到当前字符的前一个位置,计算出假设这之间没有重复字符的话,其可能的最大长度dist,但是这其中是有可能有重复字符的,比如abba,当前a距离上一个a的距离为3,但是这中间有重复字符,所以要拿这个距离跟到前一个字符不含重复字符的长度进行对比,若大于则取前一个字符最大长度+1,否则取dist就可以了,可以通过画图理一下思路,思路一旦清晰了,题目就做完了。

#define CHAR_NUM 128

int maxx(int a, int b) {
    if (a > b)
        return a;
    return b;
}

int lengthOfLongestSubstring(char* s) {
    int last[CHAR_NUM] = {0};
    int *dp = NULL;
    int len = strlen(s);
    int i = 0;
    int res = 0;
    
    dp = calloc(1, sizeof(int) * len);
    memset(last, -1, sizeof(last));
    
    for (i = 0; i < len; ++i) {
        int dist = i - last[s[i]];
        if (dist > dp[i - 1]) {
            dp[i] = dp[i - 1] + 1;
        } else {
            dp[i] = dist;
        }
        res = maxx(dp[i], res);
        last[s[i]] = i;
    }
    
    return res;
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]03.Longest Substring Without Repeating Characters

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/176.html

相关文章