我们使用贪心算法与双指针算法,在 sss 和 ttt 中分别插入两个指针,一个指针位于 sss 的起点(名为 iii ),另一个指针位于 ttt 的起点(名为 jjj )。每一步都将 iii 向前推进 111 。如果是 si=?s_i = \texttt{?}si=? ,则将其设置为 tjt_jtj 并递增 jjj 。如果是 si=tjs_i = t_jsi=tj ,那么我们也会递增 jjj (因为存在匹配)。
这样做是可行的,因为如果出现问号,那么早匹配 ttt 中的当前字符就不会比晚匹配更糟。复杂度为 O(n)\mathcal{O}(n)O(n) 。
By signing up a wangzaioj universal account, you can submit code and join discussions in all online judging services provided by us.
Using your wangzaioj universal account