484. Find Permutation

leetcode medium

#array#csharp#graph#leetcode#medium#search#stack#string

Task

Перестановка perm из n целых чисел всех чисел в диапазоне [1, n] может быть представлена в виде строки s длиной n - 1, где:

s[i] == 'I', если perm[i] < perm[i + 1], и

s[i] == 'D', если perm[i] > perm[i + 1].

Дана строка s, восстановите лексикографически наименьшую перестановку perm и верните её.

Пример:

Input: s = "I"

Output: [1,2]

Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

C# solution

matched/original

public class Solution {
    public int[] FindPermutation(string s) {
        int[] res = new int[s.Length + 1];
        Stack<int> stack = new Stack<int>();
        int j = 0;
        for (int i = 1; i <= s.Length; i++) {
            if (s[i - 1] == 'I') {
                stack.Push(i);
                while (stack.Count > 0) {
                    res[j++] = stack.Pop();
                }
            } else {
                stack.Push(i);
            }
        }
        stack.Push(s.Length + 1);
        while (stack.Count > 0) {
            res[j++] = stack.Pop();
        }
        return res;
    }
}

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>& FindPermutation(string s) {
        vector<int>& res = new int[s.size() + 1];
        stack<int> stack = new stack<int>();
        int j = 0;
        for (int i = 1; i <= s.size(); i++) {
            if (s[i - 1] == 'I') {
                stack.push(i);
                while (stack.size() > 0) {
                    res[j++] = stack.pop();
                }
            } else {
                stack.push(i);
            }
        }
        stack.push(s.size() + 1);
        while (stack.size() > 0) {
            res[j++] = stack.pop();
        }
        return res;
    }
}

Java solution

matched/original

public class Solution {
    public int[] findPermutation(String s) {
        int[] res = new int[s.length() + 1];
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 1; i <= s.length(); i++) {
            if (s.charAt(i - 1) == 'I') {
                stack.push(i);
                while (!stack.isEmpty()) {
                    res[j++] = stack.pop();
                }
            } else {
                stack.push(i);
            }
        }
        stack.push(s.length() + 1);
        while (!stack.isEmpty()) {
            res[j++] = stack.pop();
        }
        return res;
    }
}

JavaScript solution

matched/original

var findPermutation = function(s) {
    let res = new Array(s.length + 1).fill(0)
    let stack = []
    let j = 0
    for (let i = 1; i <= s.length; i++) {
        if (s[i - 1] === 'I') {
            stack.push(i)
            while (stack.length) {
                res[j++] = stack.pop()
            }
        } else {
            stack.push(i)
        }
    }
    stack.push(s.length + 1)
    while (stack.length) {
        res[j++] = stack.pop()
    }
    return res
}

Python solution

matched/original

class Solution:
    def findPermutation(self, s: str) -> List[int]:
        res = [0] * (len(s) + 1)
        stack = []
        j = 0
        for i in range(1, len(s) + 1):
            if s[i - 1] == 'I':
                stack.append(i)
                while stack:
                    res[j] = stack.pop()
                    j += 1
            else:
                stack.append(i)
        stack.append(len(s) + 1)
        while stack:
            res[j] = stack.pop()
            j += 1
        return res

Go solution

matched/original

func findPermutation(s string) []int {
    res := make([]int, len(s)+1)
    stack := []int{}
    j := 0
    for i := 1; i <= len(s); i++ {
        if s[i-1] == 'I' {
            stack = append(stack, i)
            for len(stack) > 0 {
                res[j] = stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                j++
            }
        } else {
            stack = append(stack, i)
        }
    }
    stack = append(stack, len(s)+1)
    for len(stack) > 0 {
        res[j] = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        j++
    }
    return res
}

Explanation

Algorithm

Инициализация

Создайте пустой стек stack. Создайте пустой список result для хранения конечной перестановки.

Для каждого числа i

Если текущий символ в строке s равен 'D', добавьте i в стек. Если текущий символ в строке s равен 'I', добавьте i в стек, затем извлеките все элементы из стека и добавьте их в result.

Завершение

Добавьте n в стек и извлеките все элементы из стека, добавив их в result. Верните список result, который представляет лексикографически наименьшую перестановку.

😎