阿Q的博客

[942] DI String Match

https://leetcode.com/problems/di-string-match/description/

algorithms
Easy (67.48%)
Source Code: 942.di-string-match.py
Total Accepted: 26K
Total Submissions: 37.2K
Testcase Example: '"IDID"'

Given a string S that only contains "I" (increase) or "D" (decrease), let N = S.length.

Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:

If S[i] == "I", then A[i] < A[i+1]
If S[i] == "D", then A[i] > A[i+1]

Example 1:

Input: "IDID" Output: [0,4,1,3,2]

Example 2:

Input: "III" Output: [0,1,2,3]

Example 3:

Input: "DDI" Output: [3,2,0,1]

Note:

1 <= S.length <= 10000
S only contains characters "I" or "D".

python

class Solution(object):
    def diStringMatch(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        result = []
        if not S: return result

        mn, mx = 0, len(S)

        for i in range(len(S)):
            if S[i] == 'D':
                result.append(mx)
                mx -= 1
            else:
                result.append(mn)
                mn += 1

        result.append(mn)
        return result