力扣每日一题2022-05-09简单题：增减字符串匹配

增减字符串匹配

• • 题目描述
  • 思路
  • • 贪心
    • • Python实现
      • Java实现

---

题目描述

增减字符串匹配

---

思路 贪心

从perm[0]的值开始考虑：

• 如果s[0] = ‘I’，则将perm[0]设置为0，则无论perm[1]为何值，都能比perm[0]大；
• 如果s[1] = ‘D’，则将perm[0]设置为n，则无论perm[1]为何值，都能比perm[0]小。
  确定好perm[0]后，剩余的n-1个字符和n个待确定的数就变成了一个和原问题相同，但规模为n-1的问题。可以按照上述方法确定perm[1]。如此循环直至剩下最后一个数，填入perm[n]中。

Python实现

class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        n = len(s)
        minNum, maxNum = 0, n
        perm = [0] * (n+1)
        for i, ch in enumerate(s):
            if ch == 'I':
                perm[i] = minNum
                minNum += 1
            else:
                perm[i] = maxNum
                maxNum -= 1
        perm[n] = minNum
        return perm

Java实现

class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length();
        int minNum = 0, maxNum = n;
        int[] perm = new int[n+1];
        for (int i = 0; i < n; i++) {
            perm[i] = s.charAt(i) == 'I' ? minNum++ : maxNum--;
        }
        perm[n] = minNum;
        return perm;
    }
}