增减字符串匹配

无标签

算法

发布日期: 2019-09-09

阅读次数:

题目要求

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/di-string-match
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目解法

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

接下来每次我们都可以把数的集合中的最小值或最大值取出，并放到当前的位置。即从左向右扫描字符串，如果碰到'I'就取出当前最小的数，否则取出当前最大的数。

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