1 solutions

  • 1
    @ 2024-12-9 14:03:21

    我们使用贪心算法与双指针算法,在 ss 和 tt 中分别插入两个指针,一个指针位于 ss 的起点(名为 ii ),另一个指针位于 tt 的起点(名为 jj )。每一步都将 ii 向前推进 11 。如果是 si=?s_i = \texttt{?} ,则将其设置为 tjt_j 并递增 jj 。如果是 si=tjs_i = t_j ,那么我们也会递增 jj (因为存在匹配)。

    这样做是可行的,因为如果出现问号,那么早匹配 tt 中的当前字符就不会比晚匹配更糟。复杂度为 O(n)\mathcal{O}(n) 。

    • 1

    Information

    ID
    5
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    —
    Tags
    # Submissions
    29
    Accepted
    5
    Uploaded By