美文网首页
Longest Substring Without Repeat

Longest Substring Without Repeat

作者: lanmoyingsheng | 来源:发表于2018-05-30 23:42 被阅读5次

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.

我的代码:

int lengthOfString(char* s) {
    
    int num = 0;
    while(s[num] != '\0') {
        num++;
    }
    
    return num;
}


int isHasNotRepeatCharacter(char* s) {
    
    int length = lengthOfString(s);
    
    for (int i=0; i<length-1; i++) {
        
        for (int j=i+1; j<length; j++) {
            
            if (s[i] == s[j]) {
                return 0;
            }
        }
    }
    
    return 1;
}

char* subStringFromString(char* s, int location, int length) {
    
    if (s == NULL) {
        return NULL;
    }
    
    if (lengthOfString(s) < (location + length)) {
        return NULL;
    }
    
    char *sub = (char *)malloc(sizeof(char)*length+1);
    int index = 0;
    while(index < length) {
        sub[index] = s[location + index];
        index++;
    }
    sub[index] = '\0';
    
    return sub;
}

int lengthOfLongestSubstring(char* s) {
    
    int ret = 0;
    
    int length = lengthOfString(s);
    for (int i = length; i > 0; --i) {
        for (int j = 0; j < length-i+1; ++j) {
            
            char* subString = subStringFromString(s, j, i);
            
            if(isHasNotRepeatCharacter(subString) == 1) {
                ret = lengthOfString(subString);
                free(subString);
                return ret;
            }
            free(subString);
        }
    }
    
    return ret;
}

补充:我的思路在极端情况下会出现超时的现象,例如输入的字符串特别长,待解决吧 -_- 。

相关文章

网友评论

      本文标题:Longest Substring Without Repeat

      本文链接:https://www.haomeiwen.com/subject/amlfsftx.html