| 130 | ''' |
| 131 | |
| 132 | class Solution(object): |
| 133 | def isInterleave(self, s1, s2, s3): |
| 134 | """ |
| 135 | :type s1: str |
| 136 | :type s2: str |
| 137 | :type s3: str |
| 138 | :rtype: bool |
| 139 | """ |
| 140 | """ |
| 141 | recursive. |
| 142 | """ |
| 143 | |
| 144 | if len(s3) != len(s1) + len(s2): |
| 145 | return False |
| 146 | |
| 147 | if not s3: |
| 148 | return True |
| 149 | |
| 150 | dp = {} |
| 151 | |
| 152 | # s3 index, s1, s2 |
| 153 | for i, d in enumerate(s3): |
| 154 | if i == 0: |
| 155 | temp = [] |
| 156 | if s1 and s1[0] == d: |
| 157 | temp.append((s1[1:], s2)) |
| 158 | if s2 and s2[0] == d: |
| 159 | temp.append((s1, s2[1:])) |
| 160 | dp[str(i)] = temp |
| 161 | continue |
| 162 | |
| 163 | temp = [] |
| 164 | if dp[str(i-1)]: |
| 165 | for j in dp[str(i-1)]: |
| 166 | s1, s2 = j[0], j[1] |
| 167 | if s1 and s1[0] == d: |
| 168 | if (s1[1:], s2) not in temp: |
| 169 | temp.append((s1[1:], s2)) |
| 170 | if s2 and s2[0] == d: |
| 171 | if (s1, s2[1:]) not in temp: |
| 172 | temp.append((s1, s2[1:])) |
| 173 | dp[str(i)] = temp |
| 174 | else: |
| 175 | return False |
| 176 | # print(len(dp[str(i-1)])) |
| 177 | del dp[str(i-1)] |
| 178 | |
| 179 | # print(dp) |
| 180 | try: |
| 181 | for i in dp[str(len(s3)-1)]: |
| 182 | if not any(i): |
| 183 | return True |
| 184 | else: |
| 185 | return False |
| 186 | except KeyError: |
| 187 | return False |
| 188 | |
| 189 | print(Solution().isInterleave('c'*500+'d', 'c'*500+'d', 'c'*1000+'dd')) |