摘要
Title: 97. 交错字符串
Categories: dp

97. 交错字符串

题意

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。

两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交错是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

思路

还是记忆化搜索
dp 四个状态
串a的下标串b的下标串c的下标到串a还是串b了

对于这种如果存在True的结果，就是True的dfs，所有状态的递推采取or

代码

'''
Author: NEFU AB-IN
Date: 2024-09-03 15:36:27
FilePath: \LeetCode\97\97.py
LastEditTime: 2024-09-03 16:28:52
'''
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
# 3.8.9 import
from posixpath import abspath
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:

        if len(s1) + len(s2) != len(s3):
            return False

        @lru_cache(None)
        def dfs(i1: int, i2: int, i3: int, status: bool) -> bool:
            if i1 == len(s1) and i2 == len(s2) and i3 == len(s3):
                return True
            ans = False

            if status:
                while i1 < len(s1) and i3 < len(s3):
                    if s1[i1] == s3[i3]:
                        ans = ans or dfs(i1 + 1, i2, i3 + 1, False)
                        i1, i3 = i1 + 1, i3 + 1
                    else:
                        break
            else:
                while i2 < len(s2) and i3 < len(s3):
                    if s2[i2] == s3[i3]:
                        ans = ans or dfs(i1, i2 + 1, i3 + 1, True)
                        i2, i3 = i2 + 1, i3 + 1
                    else:
                        break

            return ans

        return dfs(0, 0, 0, False) or dfs(0, 0, 0, True)