Problem#
給你兩個字串 s1 和 s2，問你 s1 的排列組合是不是 s2 的子字串，回傳所有的 index
1 | s = "cbaebabacd", p = "abc" |
- 測資限制:
- $1 \le len \le 3\cdot10^4$
想法#
枚舉任意排列 $\mathcal{O}(n!)$ 一定 TLE 所以不行這樣做。
考慮字串 s 的所有 permutation 的字元個數都相同，例如: s = "ABC" perm(s) = {"ABC", "BAC", "CAB", "ACB", "BCA", "CBA"} 不論是哪個排序都是由 1個a, 1個b, 1個c 組成
所以就不用真的去求出 permutation ，只要看 s2 的子字串的字元個數是不是和 s1 的字元個數相同即可
- 時間複雜度: $\mathcal{O}(n^2)$
- 空間複雜度: $\mathcal{O}(1)$
AC Code#
心得#
跟 Leetcode 567 - Permutation in String 一樣，只是這題要存 index