Хэш-таблица с проверкой строки

Я работаю над некоторым кодом, проверяющим повторение символа в строке. Вот какой-то ответ, который я нашел где-то.Хэш-таблица с проверкой строки

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; 
    } 
};

Это работает, и большая часть места понятна. Я просто смущен несколькими строками.

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;

Вот вопрос:

(1) Почему проверка хэша [s [я]] = - 1? s [i] - символ в строке, выше код показывает hash [i], i - от 0-256.

(2) Я смущен

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

Что это делает, пожалуйста?

источник

2015-02-13 user4441082

Почему бы не написать небольшую программу, скомпилировать ее и запустить через отладчик, чтобы увидеть, что происходит? – PaulMcKenzie

Для (1): код является ошибкой, если он не скомпилирован с неподписанными символами (в настоящее время это редко встречается в компиляторах основного ПК). s [i] предполагается, что он находится в диапазоне 0,255, что является точно набором допустимых индексов в хеш. –

Это не хэш-таблица. Переменная hash представляет собой массив int, который индексируется кодом ascii символа в строке, поэтому hash [s [i]], где s [i] == 'A' - hash [63]. Итак, что он делает, это сохранение позиции символов в массиве, индексированном символьным кодом.

hash[s[i]]!=-1 проверяет, есть вхождение символа

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; Если позиция текущего символа после начала установить начало после текущего символа.

источник

2015-02-14 00:06:02

Хэш-таблица с проверкой строки

ответ

Смежные вопросы