README_EN.md

comments	difficulty	edit_url	tags
true	Easy	https://github.com/doocs/leetcode/edit/main/solution/0900-0999/0942.DI%20String%20Match/README_EN.md	Greedy Array Two Pointers String

942. DI String Match

中文文档

Description

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'.

Solutions

Solution 1: Greedy Algorithm

We can use two pointers low and high to represent the current minimum and maximum values, respectively. Then, we traverse the string s. If the current character is I, we add low to the result array, and increment low by 1; if the current character is D, we add high to the result array, and decrement high by 1.

Finally, we add low to the result array and return the result array.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the string s.

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

func diStringMatch(s string) (ans []int) {
	low, high := 0, len(s)
	for _, c := range s {
		if c == 'I' {
			ans = append(ans, low)
			low++
		} else {
			ans = append(ans, high)
			high--
		}
	}
	ans = append(ans, low)
	return
}

TypeScript

function diStringMatch(s: string): number[] {
    const ans: number[] = [];
    let [low, high] = [0, s.length];
    for (const c of s) {
        if (c === 'I') {
            ans.push(low++);
        } else {
            ans.push(high--);
        }
    }
    ans.push(low);
    return ans;
}

Rust

impl Solution {
    pub fn di_string_match(s: String) -> Vec<i32> {
        let mut low = 0;
        let mut high = s.len() as i32;
        let mut ans = Vec::with_capacity(s.len() + 1);

        for c in s.chars() {
            if c == 'I' {
                ans.push(low);
                low += 1;
            } else {
                ans.push(high);
                high -= 1;
            }
        }

        ans.push(low);
        ans
    }
}