interleaving_string

View Source

 1from functools import cache
 2
 3
 4# @leet start
 5class Solution:
 6    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
 7        """
 8        This question asks us if we can interleave `s1` and `s2` to make `s3`.
 9        We can interleave `s1` and `s2` by checking if the first character of
10        either string is equal to `s3` and then incrementing the pointer to
11        either string.
12
13        We have to consider 6 situations:
14        1. If all three of the strings are None, we know we've created the string.
15        2. If `s1` or `s2` is None, we check if the other string equals `s3`.
16        3. If the first character of `s1`, `s2`, and `s3` are the same,
17        we can choose to increment the pointer to either string.
18        4. If only `s1` == `s3`, we can increment the pointer in `s1`,
19        5. If only `s2` == `s3`, we can increment the pointer in `s2`.
20        6. In every other case, we cannot interleave the string, so return False.
21
22        We add some caching to this in order to reduce the time complexity from
23        $O(2^m + n)$ to $O(m * n)$, with $O(m * n)$ space complexity.
24        """
25        m, n, o = len(s1), len(s2), len(s3)
26        if m + n != o:
27            return False
28
29        @cache
30        def interleave(s1, s2, s3):
31            if not s1 and not s2 and not s3:
32                return True
33            if not s1:
34                return s2 == s3
35            if not s2:
36                return s1 == s3
37            if s1[0] == s2[0] == s3[0]:
38                return interleave(s1[1:], s2, s3[1:]) or interleave(s1, s2[1:], s3[1:])
39            if s1[0] == s3[0]:
40                return interleave(s1[1:], s2, s3[1:])
41            if s2[0] == s3[0]:
42                return interleave(s1, s2[1:], s3[1:])
43            return False
44
45        return interleave(s1, s2, s3)
46
47
48# @leet end
49
50
51def test():
52    assert 2 + 2 == 4

class Solution: View Source

 6class Solution:
 7    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
 8        """
 9        This question asks us if we can interleave `s1` and `s2` to make `s3`.
10        We can interleave `s1` and `s2` by checking if the first character of
11        either string is equal to `s3` and then incrementing the pointer to
12        either string.
13
14        We have to consider 6 situations:
15        1. If all three of the strings are None, we know we've created the string.
16        2. If `s1` or `s2` is None, we check if the other string equals `s3`.
17        3. If the first character of `s1`, `s2`, and `s3` are the same,
18        we can choose to increment the pointer to either string.
19        4. If only `s1` == `s3`, we can increment the pointer in `s1`,
20        5. If only `s2` == `s3`, we can increment the pointer in `s2`.
21        6. In every other case, we cannot interleave the string, so return False.
22
23        We add some caching to this in order to reduce the time complexity from
24        $O(2^m + n)$ to $O(m * n)$, with $O(m * n)$ space complexity.
25        """
26        m, n, o = len(s1), len(s2), len(s3)
27        if m + n != o:
28            return False
29
30        @cache
31        def interleave(s1, s2, s3):
32            if not s1 and not s2 and not s3:
33                return True
34            if not s1:
35                return s2 == s3
36            if not s2:
37                return s1 == s3
38            if s1[0] == s2[0] == s3[0]:
39                return interleave(s1[1:], s2, s3[1:]) or interleave(s1, s2[1:], s3[1:])
40            if s1[0] == s3[0]:
41                return interleave(s1[1:], s2, s3[1:])
42            if s2[0] == s3[0]:
43                return interleave(s1, s2[1:], s3[1:])
44            return False
45
46        return interleave(s1, s2, s3)

def isInterleave(self, s1: str, s2: str, s3: str) -> bool: View Source

 7    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
 8        """
 9        This question asks us if we can interleave `s1` and `s2` to make `s3`.
10        We can interleave `s1` and `s2` by checking if the first character of
11        either string is equal to `s3` and then incrementing the pointer to
12        either string.
13
14        We have to consider 6 situations:
15        1. If all three of the strings are None, we know we've created the string.
16        2. If `s1` or `s2` is None, we check if the other string equals `s3`.
17        3. If the first character of `s1`, `s2`, and `s3` are the same,
18        we can choose to increment the pointer to either string.
19        4. If only `s1` == `s3`, we can increment the pointer in `s1`,
20        5. If only `s2` == `s3`, we can increment the pointer in `s2`.
21        6. In every other case, we cannot interleave the string, so return False.
22
23        We add some caching to this in order to reduce the time complexity from
24        $O(2^m + n)$ to $O(m * n)$, with $O(m * n)$ space complexity.
25        """
26        m, n, o = len(s1), len(s2), len(s3)
27        if m + n != o:
28            return False
29
30        @cache
31        def interleave(s1, s2, s3):
32            if not s1 and not s2 and not s3:
33                return True
34            if not s1:
35                return s2 == s3
36            if not s2:
37                return s1 == s3
38            if s1[0] == s2[0] == s3[0]:
39                return interleave(s1[1:], s2, s3[1:]) or interleave(s1, s2[1:], s3[1:])
40            if s1[0] == s3[0]:
41                return interleave(s1[1:], s2, s3[1:])
42            if s2[0] == s3[0]:
43                return interleave(s1, s2[1:], s3[1:])
44            return False
45
46        return interleave(s1, s2, s3)

This question asks us if we can interleave s1 and s2 to make s3. We can interleave s1 and s2 by checking if the first character of either string is equal to s3 and then incrementing the pointer to either string.

We have to consider 6 situations:

If all three of the strings are None, we know we've created the string.
If s1 or s2 is None, we check if the other string equals s3.
If the first character of s1, s2, and s3 are the same, we can choose to increment the pointer to either string.
If only s1 == s3, we can increment the pointer in s1,
If only s2 == s3, we can increment the pointer in s2.
In every other case, we cannot interleave the string, so return False.

We add some caching to this in order to reduce the time complexity from $O(2^m + n)$ to $O(m * n)$, with $O(m * n)$ space complexity.

def test(): View Source

52def test():
53    assert 2 + 2 == 4