0942._DI_String_Match.md

942. DI String Match

难度: Easy

刷题内容

原题连接

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

内容描述

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".

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

• 按照I出现的顺序依次assign 值 0 到 i
• 按照D出现的顺序依次assign 值 N 到 i+2
• 最后一个数字就是i+1

sb题没什么好说的

class Solution:
    def diStringMatch(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        if not S or len(S) == 0:
            return [0]
        res = [0] * (len(S)+1)
        idx1 = 0
        idx2 = len(S)
        for i in range(len(S)):
            if S[i] == 'I':
                res[i] = idx1
                idx1 += 1
            else:
                res[i] = idx2
                idx2 -= 1
        res[-1] = idx1 
        return res