leetcode solution

KMP 算法本质 This is a very good KMP algorithm article if you can read Chinese:  KMP algorithm .  But it still doesn't clear state what known information is used to reduce comparison. I figured this out by myself.  The "known information" is the longest unique substring. Last Step The naive  solution what it fails to match ' ' with 'D', it will reset j = 0, and i = 5 to re-match the whole string from beginning. Therefore the "known information" S[5] == P[1] == B, S[6] == P[2] == C, S[7] == P[3] == D, and S[8] == P[4] == A is discarded.  The KMP algorithm is utilizing this info to reduce comparison. Since we know P[0] != P[1] != P[2] != P[3] and P[0] == P[4] == A,  there is no necessary to compare P[0] with S[5], S[6], S[7], S[8]. Why? Because we know S[5] == P[1] == B, and P[0] != P[1], therefore, P[0] != S[5], similarly, P[0] cannot be S[6], S[7] either. Since P[0] == P[4] == A, we cannot skip S[8], that's why we start wit...

3 - Pointers  (i : begin of interest, j : end of interest, storeIndex, in place save position) 151 Reverse Words in a String    reverse the whole string and then reverse each word. Specifically, use 3 pointers. One denote the beginning of a new char, another denote the end of a new char, a third pointer to keep track of the sotre position in the current char (since there maybe multiple space between words, storeIndex <= j) 443 String Compression   Similar to 151  Reverse Words in a String ,  i  will keep track of start position of current repeating char,  j  will be the end of the repeating char group, storeIndex will keep track where to save the current unique char and its occurrence. DP 5 Longest Palindromic Substring Base case1: all 1-length string is palindrome Base case2:  check all s[i][i+1] length 2 string by comparison s[i] with s[i+1] DP function 2, transition formula for substring lengt...

Counters 657  Judge Route Circle Define two counter and loop over each char in the string, if encounter char 'U' increase counter1 by 1, if encounter char 'D' decrease counter 1 by 1. Similarly for 'L', 'R' using counter2. Finally check whether both the two counters are equal to 0. 383  Ransom Note (1) Loop over all the chars in the magazine and count all the char frequency in the magazine incrementally (2) Loop over all the chars in the  ransom note and then decrease the char frequency in the ransom note, if eventually all the char frequency still greater or equal than zero, meaning we can construct the ransom note from the magazine, otherwise we cannot. 387  First Unique Character in a String Define a hashMap (unordered_map in C++) Loop the string twice, the first loop count the frequency of each char and save the result in the map The second loop, loop each char from the beginning, once find a char has frequency 1 in the map, return its i...