942. DI String Match

leetcode easy

#array#csharp#easy#leetcode#string#two-pointers

Task

Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] может быть представлена в виде строки s длины n, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Получив строку s, восстановите перестановку perm и верните ее. Если существует несколько допустимых перестановок perm, верните любую из них.

Пример:

Input: s = "IDID"

Output: [0,4,1,3,2]

C# solution

matched/original

public class Solution {
    public int[] DiStringMatch(string s) {
        int n = s.Length;
        int low = 0, high = n;
        int[] perm = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            if (s[i] == 'I') {
                perm[i] = low++;
            } else {
                perm[i] = high--;
            }
        }
        
        perm[n] = low;
        return perm;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& DiStringMatch(string s) {
        int n = s.size();
        int low = 0, high = n;
        vector<int>& perm = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            if (s[i] == 'I') {
                perm[i] = low++;
            } else {
                perm[i] = high--;
            }
        }
        
        perm[n] = low;
        return perm;
    }
}

Java solution

matched/original

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

JavaScript solution

matched/original

var diStringMatch = function(s) {
    const n = s.length;
    let low = 0, high = n;
    const perm = new Array(n + 1);
    
    for (let i = 0; i < n; i++) {
        if (s[i] === 'I') {
            perm[i] = low++;
        } else {
            perm[i] = high--;
        }
    }
    
    perm[n] = low;
    return perm;
};

Python solution

matched/original

def diStringMatch(s):
    n = len(s)
    low, high = 0, n
    perm = [0] * (n + 1)
    
    for i in range(n):
        if s[i] == 'I':
            perm[i] = low
            low += 1
        else:
            perm[i] = high
            high -= 1
    
    perm[n] = low
    return perm

Go solution

matched/original

package main

func diStringMatch(s string) []int {
    n := len(s)
    low, high := 0, n
    perm := make([]int, n+1)
    
    for i := 0; i < n; i++ {
        if s[i] == 'I' {
            perm[i] = low
            low++
        } else {
            perm[i] = high
            high--
        }
    }
    
    perm[n] = low
    return perm
}

Explanation

Algorithm

Инициализировать два указателя low и high для отслеживания минимального и максимального числа, которые можно использовать в перестановке.

Создать массив perm длиной n + 1.

Пройти по строке s:

Если текущий символ равен 'I', добавить low в текущую позицию perm и увеличить low.

Если текущий символ равен 'D', добавить high в текущую позицию perm и уменьшить high.

Добавить оставшееся значение (low или high, так как они будут равны) в последнюю позицию perm.

Вернуть массив perm.

😎