CODEWITHSUNDEEP
c++hashtable
user4441082
user4441082

Reputation: 371

Hash table with string check

I am working on some code checking the repeat of character in a string. Here is some answer I found somewhere.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[256];
        for(int i=0; i<256; i++) hash[i] = -1;
        int start = 0, ans = 0;
        int i;
        for(i=0; i<s.size(); i++){
            if( -1 != hash[ s[i] ] ){
                if(ans < i-start) ans = i-start;//update max length
                for(int j=start; j<hash[ s[i] ]; j++) hash[j] = -1;
                if(hash[ s[i] ] + 1  > start )
                   start = hash[ s[i] ] +1;//update start if repeat happen
            }
            hash[ s[i]] = i;
        }
        if(ans < i-start) ans = i-start;
        return ans;
    }
};

It works, and most of the place is clear. I am just confused at several lines. 

if( -1 != hash[ s[i] ] ){
                if(ans < i-start) ans = i-start;//update max length
                for(int j=start; j<hash[ s[i] ]; j++) hash[j] = -1;
                if(hash[ s[i] ] + 1  > start )
                   start = hash[ s[i] ] +1;
            }
            hash[ s[i]] = i;

Here are question:

(1) Why checking hash[s[i]]!=-1? s[i] is character in the string, above code shows hash[i], i is from 0-256.

(2) I am confused at

for(int j=start; j<hash[ s[i] ]; j++) hash[j] = -1;
                    if(hash[ s[i] ] + 1  > start )
                       start = hash[ s[i] ] +1;

What is it doing please?

Upvotes: 0

Views: 182

Answers (1)

Tasos Vogiatzoglou
Tasos Vogiatzoglou

Reputation: 2453

That's not a hashtable. The hash variable is an array of int that's indexed by the ascii code of the char in the string, so hash[s[i]] where s[i]=='A' is hash[63]. So, what it does is storing the characters' position in an array indexed by the character code.

hash[s[i]]!=-1 checks if there is an occurrence of the character

for(int j=start; j From start to the current position of the character set hash[position] to -1. This must be either buggy or misintended as it mixes the character-based index of hash with the positional nature of j.

if(hash[ s[i] ] + 1 > start ) start = hash[ s[i] ] +1; If the position of the current character is after start set start after the current character.

Upvotes: 1

Related Questions