add some comments for "Minimum Window Substring"

haoel · haoel · commit ab5348c1eb32 · 2015-02-04T11:47:25.000+08:00
diff --git a/src/minimumWindowSubstring/minimumWindowSubstring.cpp b/src/minimumWindowSubstring/minimumWindowSubstring.cpp
@@ -34,7 +34,11 @@ using namespace std;
 string minWindow(string S, string T) {
     string win;
     if (S.size()<=0 || T.size()<=0 || T.size() > S.size()) return win;
-    
+    /*
+     * Declare two "hash map" for ASCII chars
+     *   f[]: represents the char found in string S
+     *   m[]: stores the chars in string T
+     */    
     const int MAX_CHARS = 256;
     int f[MAX_CHARS], m[MAX_CHARS];
     
@@ -43,6 +47,10 @@ string minWindow(string S, string T) {
     memset(m, NOT_EXISTED, sizeof(m));
     memset(f, NOT_EXISTED, sizeof(f));
 
+    /* 
+     *  Go through the T, and inital the m[] and f[] 
+     *  Notes: a same char can be appeared multiple times.
+     */
     for(int i=0; i<T.size(); i++) {
         m[T[i]]==NOT_EXISTED ? m[T[i]]=1 : m[T[i]]++ ; 
         f[T[i]] = NOT_FOUND; 
@@ -53,20 +61,28 @@ string minWindow(string S, string T) {
     int letterFound = 0;
     int begin = 0;
     for(int i=0; i<S.size(); i++) {
-        
+        /* if S[i] is existed in T*/ 
         if ( m[S[i]] != NOT_EXISTED ){
             char ch = S[i];
             f[ch]++;
+
+            /* if one char has been found enough times, then do not do letterFound++ */
             if (f[ch] <= m[ch]) {
                 letterFound++;
             }
             if ( letterFound >= T.size() ) {
+                /* 
+                 * Find the beginning of the window
+                 * 1) f[S[begin]] == NOT_EXISTED  ===> the char at the `begin` is not in T
+                 * 2) f[S[begin]] > m[S[begin]]   ===> a same char appeared more than excepted.
+                 */
                 while ( f[S[begin]] == NOT_EXISTED || f[S[begin]] > m[S[begin]] ) { 
                     if ( f[S[begin]] > m[S[begin]] ) {
                         f[S[begin]]--;
                     }   
                     begin++;
                 }
+                /* Calculate the minimized window size */
                 if(winSize > i - begin + 1){
                     start = begin;
                     winSize = i - begin + 1;
