前往
大廳
主題

[leetcode]76. Minimum Window Substring

♙♲⚙\~O_O~/⚙♲♙ | 2021-08-19 12:00:08 | 巴幣 2 | 人氣 309

題目: 76. Minimum Window Substring
難度: Hard
目前下列解法的時間複雜度: O(m+n)


題目說明

給定兩字串 s 及 t 長度分別為 m 及 n。
求最小長度的 s 子字串,使得所有在 t 中出現的字元都在此子字串中出現且出現次數 >= 該字元在 t 中出現的次數。


解法: 兩個指針一加一減刷過去

0. 先算一下 t 幾個字元、每個字元出現的次數,直接存陣列。
1. 訂好左右指針,右邊的指針刷過去把上面陣列存的次數減少;左邊的增加。
2. 當次數都歸 0 時比一下長度,比較短就記下來。使用"總共還剩幾個字元"的方式避免刷 一次字元集合。


source code

然後想說用指標寫,結果還是到 4ms 。Q_Q

創作回應

相關創作

更多創作