4ms C code in 12 lines


  • 31
    T
    int lengthOfLongestSubstring(char* s)
    {
    	int len=0;
        char *end=s,*temp;
    	char* addressTable[128]={NULL};
    	while(*end){
    		temp = addressTable[*end];
    		addressTable[*end]=end;
    		if(temp>=s){
    		len=end-s>len?end-s:len;
    		s = temp+1;
    		}end++;
    	}
    	len=end-s>len?end-s:len;
    	return len;
    }

  • 1
    T

    nice method!!!!


  • 1
    L

    Really Nice ~~


  • 0
    A

    nice and concise code.I have a question,what the function of the addresstable[]?Can it get the closet position of char s?If so,what the code of it?


  • 8
    D

    can someone please explain the code.


  • 0
    R

    don't delete the element before the repeated character ? if the string is "dvqrevdiok"


  • 1
    X

    @deepvkk
    addressTable[*c] represent the character '*c' 's pointer in origin string


  • 0
    G

    @deepvkk
    int lengthOfLongestSubstring(char* s)
    {
    int len=0;
    char *end=s,temp;
    char
    addressTable[128]={NULL};
    while(*end){
    temp = addressTable[*end];
    addressTable[*end]=end;
    if(temp>=s){ // s piont to the beginning of current substring , temp piont to the last repeat char ,if temp < s ignoring;
    len=end-s>len?end-s:len; // (end -s) length of current substring
    s = temp+1; // piont to new char
    }end++;
    }
    len=end-s>len?end-s:len;
    return len;
    }


  • 0
    2

    how does it work! sorry,as a newbie,to be honest,i can understand your code.
    And your are great by pass it by 4 ms.


  • 3
    6

    @2689590326
    That's a piece of excellent code!

    1. *end is the character's ascii number,
    2. and we use the ascii number as the index of addressTable
    3. what stored in the addressTable is the character's address
    4. At first, every pointer in addressTable is initialized as NULL
    5. and pointer s and end are at the start of the string
    6. As the while clause proceeds, the pointer end 'register' every character(of that string)'s address into the addressTable of the index(which is the exact ascii number of that character)
    7. when end encounters a same ascii number , the if clause will handle this
    8. what the if clause will do is recording the length of current substring(specified between s and end, calculated by end-s) and then update s to temp+1
    9. temp stores the older same character's address

  • 0
    A

    perfect pointer moving!!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.