原文链接: https://leetcode-cn.com/problems/di-string-match

英文原文

A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:

• s[i] == 'I' if perm[i] < perm[i + 1], and
• s[i] == 'D' if perm[i] > perm[i + 1].

Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

• 1 <= s.length <= 105
• s[i] is either 'I' or 'D'.

中文题目

给定只含 "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]

 

示例 1：

输入："IDID"
输出：[0,4,1,3,2]

示例 2：

输入："III"
输出：[0,1,2,3]

示例 3：

输入："DDI"
输出：[3,2,0,1]

 

提示：

• 1 <= S.length <= 10000
• S 只包含字符 "I" 或 "D"。

通过代码

官方题解

分析

我们首先考虑字符串中的第一个字母。如果 S[0] == 'I'，那么我们只要令 A[0] = 0，就一定能满足 A[0] < A[1]。如果 S[0] == 'D'，同样我们只要令 A[0] = N，就一定能满足 A[0] > A[1]。

接下来，当我们考虑 S 中剩下的 N - 1 个字母时，还剩下 N 个数可以使用，这 N 个数为 [0 .. N - 1] 或 [1 .. N]。可以发现，由于 S[0] 的值已经确定，那么剩下 S 中的 N - 1 个字母和 N 个可用的数变成了一个和原问题相同，但规模为 N - 1 的问题。即如果 S[1] == 'I'，我们就令 A[1] 为剩下数中最小的那个数；如果 S[1] == 'D'，我们就令 A[1] 为剩下数中最大的那个数。

我们每次会把可以使用的数的集合中的最小值或最大值取出，并放到当前的位置，因此可以使用的数的集合总是连续的，就可以非常方便的进行维护。

算法

我们维护当前未使用的最小和最大的数，它们对应的区间为当前未使用的数的集合。从左向右扫描字符串，如果碰到 'I'，就取出当前最小的数，否则取出当前最大的数。

[sol1]
class Solution {
    public int[] diStringMatch(String S) {
        int N = S.length();
        int lo = 0, hi = N;
        int[] ans = new int[N + 1];
        for (int i = 0; i < N; ++i) {
            if (S.charAt(i) == 'I')
                ans[i] = lo++;
            else
                ans[i] = hi--;
        }

        ans[N] = lo;
        return ans;
    }
}

[sol1]
class Solution(object):
    def diStringMatch(self, S):
        lo, hi = 0, len(S)
        ans = []
        for x in S:
            if x == 'I':
                ans.append(lo)
                lo += 1
            else:
                ans.append(hi)
                hi -= 1

        return ans + [lo]

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是字符串 S 的长度。

• 空间复杂度：$O(N)$。

统计信息

通过次数	提交次数	AC比率
23459	32093	73.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言