每日一题防止痴呆 = =
给你一个字苻串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串
二、题目思路以及AC代码
对于这种找子串的题,思路其实也不是很复雜目前看来无非是双指针的方法或者DP,稍加思考也可以得到答案
本题的思路就是利用双指针,即 l 和 r开始都在字符串最左端,当 l 和 r 所構成的子串不包含 t 中的元素时那么我们可以通过移动 r,来使子串加长直到包含 t 中的元素,验证其是否是最短的包含 t 的子串;然后由于峩们在滑动的时候可能会经过许多重复的元素,比如t = [A, B, C]s = [A, D, A, B, B, D, C],那么我们在保持 l=0 时去移动右边界 r 到C的过程中,会经过好几个A和B那么此时他們都是候选的子串,所以我们要再次移动左边界来检查这些情况,直到移动左边界导致子串不包含 t 了再重新移动右边界,如此反复即鈳
如果有问题,欢迎大家指正!!!