DI String Match

We can solve this problem by keeping track of the smallest and largest elements we haven’t placed. If we encounter an ‘I’, place the small element; otherwise place the large element.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        # Initialize left and right pointers.
        left = 0
        right = len(s)

        # Initialize an empty list to store the result.
        result = []

        # Loop through the string s.
        for i in s:
            # If the character is 'I', append the current smallest number, then increment left.
            if i == 'I':
                result.append(left)
                left += 1

            # If the character is 'D', append the current largest number, then decrement right.
            else:
                result.append(right)
                right -= 1

        # At the end, left and right are pointing to the same number. 
        # Append this number to the result as the last element.
        result.append(left)

        return result

In this code, we start with ’left’ at 0 and ‘right’ at len(s), and as we traverse the input string, we choose either the ’left’ or the ‘right’ number depending on whether the current character is ‘I’ or ‘D’. If the character is ‘I’, we know that we need to place a number smaller than the next one, so we use ’left’ (the smallest number we haven’t placed), and then increment ’left’. If the character is ‘D’, we know that we need to place a number larger than the next one, so we use ‘right’ (the largest number we haven’t placed), and then decrement ‘right’. After we traverse the input string, we still need to place one number, which is the number that both ’left’ and ‘right’ are pointing to. We append this number to the result and then return the result.