feat: add typescript solution to lc problem: No.0076.Minimum Window Substring (doocs#458)

zhaocchen · web-flow · commit 74cc0dc699e3 · 2021-06-16T18:49:23.000+08:00
diff --git a/solution/0000-0099/0076.Minimum Window Substring/README.md b/solution/0000-0099/0076.Minimum Window Substring/README.md
@@ -40,6 +40,8 @@
 
 ## 解法
 
+滑动窗口
+
 <!-- 这里可写通用的实现逻辑 -->
 
 <!-- tabs:start -->
@@ -60,6 +62,46 @@
 
 ```
 
+### **TypeScript**
+
+```ts
+function minWindow(s: string, t: string): string {
+    let n1 = s.length, n2 = t.length;
+    if (n1 < n2) return '';
+    let need = new Array(128).fill(0);
+    let window = new Array(128).fill(0);
+    for (let i = 0; i < n2; ++i) {
+        ++need[t.charCodeAt(i)];
+    }
+
+    let left = 0, right = 0;
+    let res = '';
+    let count = 0;
+    let min = n1 + 1;
+    while (right < n1) {
+        let cur = s.charCodeAt(right);
+        ++window[cur];
+        if (need[cur] > 0 && need[cur] >= window[cur]) {
+            ++count;
+        }
+        while (count == n2) {
+            cur = s.charCodeAt(left);
+            if (need[cur] > 0 && need[cur] >= window[cur]) {
+                --count;
+            }
+            if (right - left + 1 < min) {
+                min = right - left + 1;
+                res = s.slice(left, right + 1);
+            }
+            --window[cur];
+            ++left;
+        }
+        ++right;
+    }
+    return res;
+};
+```
+
 ### **...**
 
 ```
diff --git a/solution/0000-0099/0076.Minimum Window Substring/README_EN.md b/solution/0000-0099/0076.Minimum Window Substring/README_EN.md
@@ -43,6 +43,46 @@
 
 ```
 
+### **TypeScript**
+
+```ts
+function minWindow(s: string, t: string): string {
+    let n1 = s.length, n2 = t.length;
+    if (n1 < n2) return '';
+    let need = new Array(128).fill(0);
+    let window = new Array(128).fill(0);
+    for (let i = 0; i < n2; ++i) {
+        ++need[t.charCodeAt(i)];
+    }
+
+    let left = 0, right = 0;
+    let res = '';
+    let count = 0;
+    let min = n1 + 1;
+    while (right < n1) {
+        let cur = s.charCodeAt(right);
+        ++window[cur];
+        if (need[cur] > 0 && need[cur] >= window[cur]) {
+            ++count;
+        }
+        while (count == n2) {
+            cur = s.charCodeAt(left);
+            if (need[cur] > 0 && need[cur] >= window[cur]) {
+                --count;
+            }
+            if (right - left + 1 < min) {
+                min = right - left + 1;
+                res = s.slice(left, right + 1);
+            }
+            --window[cur];
+            ++left;
+        }
+        ++right;
+    }
+    return res;
+};
+```
+
 ### **...**
 
 ```
diff --git a/solution/0000-0099/0076.Minimum Window Substring/Solution.ts b/solution/0000-0099/0076.Minimum Window Substring/Solution.ts
@@ -0,0 +1,35 @@
+function minWindow(s: string, t: string): string {
+    let n1 = s.length, n2 = t.length;
+    if (n1 < n2) return '';
+    let need = new Array(128).fill(0);
+    let window = new Array(128).fill(0);
+    for (let i = 0; i < n2; ++i) {
+        ++need[t.charCodeAt(i)];
+    }
+
+    let left = 0, right = 0;
+    let res = '';
+    let count = 0;
+    let min = n1 + 1;
+    while (right < n1) {
+        let cur = s.charCodeAt(right);
+        ++window[cur];
+        if (need[cur] > 0 && need[cur] >= window[cur]) {
+            ++count;
+        }
+        while (count == n2) {
+            cur = s.charCodeAt(left);
+            if (need[cur] > 0 && need[cur] >= window[cur]) {
+                --count;
+            }
+            if (right - left + 1 < min) {
+                min = right - left + 1;
+                res = s.slice(left, right + 1);
+            }
+            --window[cur];
+            ++left;
+        }
+        ++right;
+    }
+    return res;
+};
