commit changes to gh-pages aug 25

tg123 · tg123 · commit 16765a341117 · 2014-08-25T00:32:41.000+08:00
diff --git a/_includes/_root/minimum-window-substring/README.md b/_includes/_root/minimum-window-substring/README.md
@@ -1,4 +1,79 @@
+## What is window substring like
+
+```
+S = "ADOBECODEBANC"
+T = "ABC"
+```
+
+Minimum window is "BANC". A string with 1 `A`, 1 `B` and 1 `C`.
+
+Something you shuold notice:
+ 
+ * if a substring is a window string, it plus any string is also a window string.
+
+  `ADOBEC` is a window string, so `ADOBECODE` is a window string too.
+
+ * if a window string's left most or right most character, lets say `c`, is in `T` and the window string has more character `c` than `T` has, removing the `c` from the window string will not break that the remaining string is a window string.
+
+  `ADOBECODEBA` has 2 `A`, and more than `T` has (1 `A`). so, after remove `A` from left or right, the string remains a window string (`ADOBECODEB` is a window string).
+  
+
+## Loop invariant to find all possiable window string
+
+Assume that we had found a window string, `W`.
+
+Then
+
+ 1. When a new char comes, `W` + new char = `WN`  is also a window. (Rule 1)
+ 1. Trim the new window string, `WN`, from the left part, remove any char that is redundant to have a window string. (Rule 2)
+
+Code looks like
+
+```
+
+W = a window string in S
+
+foreach c after W in S
+  
+  WN = W + c
+  
+  // Trim left
+  
+  foreach _c in WN
+  
+    if _c can be remove from WN
+      remove _c from the left part of WN
+    else
+      break
+   
+  W = WN
+
+```
+
+### Finding the first `W`
+
+the `W` should have any char in `T`, this problem is like the `Check concatenation using count sum` in [Substring with Concatenation of All Words](../substring-with-concatenation-of-all-words).
+
+Use a map `need`, stores how many chars are needed.
+
+Use a map `seen`, stores how many chars are seen.
+
+Those maps are not only used in finding `W`, but also in triming redundant from `WN`.
+
+
+This last problem is when the `W` is found.
+Like [Substring with Concatenation of All Words](../substring-with-concatenation-of-all-words), just use a `counter`,
+When `seen` is added, just add 1 to the counter.
+
+The time `counter == T.length` is the time we first found `W`.
+
+
+
+_Note_: 
+a char in `seen[c]` can contribute at most `need[c]` count to the `counter`.
+
+
+
+
 
-## TODO 
-  * write down thinking
 
diff --git a/_includes/_root/wildcard-matching/README.md b/_includes/_root/wildcard-matching/README.md
@@ -1,4 +1,62 @@
+## Convert to [Regular Expression Matching](../regular-expression-matching)
 
-## TODO 
-  * write down thinking
+ * `?` -> `.`
+ * `*` -> `.*`
 
+This should work, yet, it exceeds the time limited. 
+
+## Checkpoint / Timemachine
+
+On modern OS, you can go back to some time you saved if your OS meets some problem.
+such technology also can be used to solve this problem.
+
+```
+    S
+ 
+[ a a b ]
+ 
+[ a * b * ]
+ 
+    P
+ 
+ 
+P is *, save current state. 
+```
+
+`P` goes on to next
+
+```
+
+This state means * matches nothing
+
+    S
+ 
+[ a a b ]
+ 
+[ a * b * ]
+ 
+      P
+
+```
+
+a mismatch found, `P != S`, so rollback to checkpoint.
+
+```
+This state means * matches a
+
+      S
+ 
+[ a a b ]
+ 
+[ a * b * ]
+ 
+      P
+```
+
+Each `*` will save to a checkpoint, and retry from nothing until a match is found.
+
+
+### Remaining tail
+
+Sometimes, `S` meets the end, but the `P` not. 
+In this case, just to check remaining chars in `P` are all `*`.
diff --git a/minimum-window-substring/index.md b/minimum-window-substring/index.md
@@ -1,7 +1,8 @@
 ---
 layout: solution
 title: Minimum Window Substring
-date: 2014-07-23 02:42:48 +0800
+date: 2014-08-25 00:31:17 +0800
+eaten: true
 ---
 {% assign leetcode_name = {{page.path | remove: '/index.md'}}  %}
 {% assign leetcode_readme = {{leetcode_name | append: '/README.md' | prepend: '_root/' }}  %}
diff --git a/wildcard-matching/index.md b/wildcard-matching/index.md
@@ -1,7 +1,8 @@
 ---
 layout: solution
 title: Wildcard Matching
-date: 2014-07-23 02:42:48 +0800
+date: 2014-08-23 13:09:31 +0800
+eaten: true
 ---
 {% assign leetcode_name = {{page.path | remove: '/index.md'}}  %}
 {% assign leetcode_readme = {{leetcode_name | append: '/README.md' | prepend: '_root/' }}  %}
