Leetcode-Easy 942. DI String Match

题目描述

给定仅包含“I”（增加）或“D”（减少）的字符串S，令N = S.length。

返回[0,1，...，N]的任何排列A，使得对于所有i = 0，...，N-1：

• 如果S [i] ==“I”，那么A [i] <A [i + 1]
• 如果S [i] ==“D”，那么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]

思路

• 我们可以用的数字是一个整数数组[0,1,2,...,len(S)]
• 当看到“I”时，最安全的选择就是为下次移动设置最低（最左边）的数字，所以它总会增加
• 当看到“D”时，最安全的选择是为下次移动放置最高（最右边）的数字，所以它总会减少
• 最后放入当lo==hi的数字

代码实现

class Solution:
    def diStringMatch(self, S: 'str') -> 'List[int]':
        lo,hi=0,len(S)
        ans=[]
        for x in S:
            if x=='I':
                ans.append(lo)
                lo+=1
            if x=='D':
                ans.append(hi)
                hi-=1
        return ans+[hi]
        # return ans+[hi] 和上语句同样效果，此时lo==hi

思路来自：https://leetcode.com/problems/di-string-match/solution/

其实我们发现返回的结果不一定是唯一的，例如S='IDID'时，我们方法得出的结果是[0,4,1,3,2],但是像[1,4,0,3,2]，[0,4,2,3,1]也是符合题意的。这个思路可以理解是贪婪算法，然后我们每次求的都是最优解。