增减字符串匹配 图解题解

只含 I 和 D 的串，要还原成怎样的排列

给一个只含 'I' 和 'D'、长度为 n 的字符串 s，要造一个由 0 到 n 这 n+1 个不同整数组成的排列 perm：s 第 i 位是 'I' 就得 perm[i]＜perm[i+1]，是 'D' 就得 perm[i]＞perm[i+1]。合法答案可能不止一个，返回任意一个即可。题面例子 s="IDID"，一个合法输出是 [0,4,1,3,2]。

把全排列都排出来逐个验，要试多少个

一个直接的办法，是把 0 到 n 的全排列一个个列出来，逐个检查每一位的增减关系对不对。可 n+1 个数的排列有 (n+1)! 种，阶乘级往上蹿，n 才十几就是上亿个，光是列完都跑不动。O((n+1)!·n) 这条路一开始就走不通。

'I' 该先给最小、'D' 该先给最大

手里攥着一段还没用过的连续整数，最小的记 low、最大的记 high。轮到 'I'，它要求后一位更大，那就把当前最小的 low 填进去——剩下没用的数全都比 low 大，后面无论接什么都拉得起这个『更大』。轮到 'D'，它要求后一位更小，就填当前最大的 high——剩下的数全比 high 小，后面那位怎么填都够小。每填一个，用掉的正好是区间的一端，剩下的仍是一段连续整数，下一步照样有最小、最大可取，不会填到中途没数可用。

两个指针怎么走，末尾为什么要单独补一格

low 从 0 起、high 从 n 起，从左到右扫 s：遇 'I' 把 low 填进答案、low 加一；遇 'D' 把 high 填进答案、high 减一。扫完 s 的 n 个字符，答案里只有 n 个数，可位置有 n+1 个——循环只填了前 n 位。这时 low 恰好等于 high，正是区间收到最后剩下的那一个数，把它补到末位，n+1 个位置才填满。

s="IDID" 四个字符，逐位填出 [0,4,1,3,2]

初始 low=0、high=4。第 0 位 'I'：填 low=0，low 变 1，答案 [0]。第 1 位 'D'：填 high=4，high 变 3，答案 [0,4]。第 2 位 'I'：填 low=1，low 变 2，答案 [0,4,1]。第 3 位 'D'：填 high=3，high 变 2，答案 [0,4,1,3]。四个字符扫完，此时 low 和 high 都等于 2，补到末位，得 [0,4,1,3,2]。回头核一眼：0＜4、4＞1、1＜3、3＞2，四段增减和 "IDID" 一位不差。

全 I、全 D 的串会填成什么样

全是 'I' 时每步都取 low，从 0 一路递增到 n，s="III" 填出 [0,1,2,3]；全是 'D' 则每步取 high，从大到小排成倒序。两种极端都自然落进同一套规则，用不着写特判。

循环一结束就返回，会少补那最后的 low，答案就短一位，根本凑不齐 0 到 n 的排列；把 'I' 填 high、'D' 填 low 放反，增减关系全体翻转，"IDID" 头一段就对不上。时间上从左到右扫一遍是 O(n)，只用 low、high 两个指针、不算输出数组是 O(1)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        low, high = 0, len(s)
        ans = []
        for c in s:
            if c == "I":
                ans.append(low)
                low += 1
            else:
                ans.append(high)
                high -= 1
        ans.append(low)
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n = s.size();
        int low = 0, high = n;
        vector<int> ans(n + 1);
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'I') {
                ans[i] = low++;
            } else {
                ans[i] = high--;
            }
        }
        ans[n] = low;
        return ans;
    }
};

Java

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