1190. Reverse Substrings Between Each Pair of Parentheses

LeetCode medium оригинал: C# #csharp #leetcode #medium #stack #string #tree

LeetCode Static

Дана строка s, состоящая из строчных букв английского алфавита и скобок.

Переверните строки в каждой паре соответствующих скобок, начиная с самой внутренней.

Ваш результат не должен содержать скобок.

Пример:

Input: s = "(abcd)"

Output: "dcba"

C# решение

сопоставлено/оригинал

public class Solution {
    public string ReverseParentheses(string s) {
        Stack<int> openParenthesesIndices = new Stack<int>();
        StringBuilder result = new StringBuilder();
        foreach (char currentChar in s) {
            if (currentChar == '(') {
                openParenthesesIndices.Push(result.Length);
            } else if (currentChar == ')') {
                int start = openParenthesesIndices.Pop();
                Reverse(result, start, result.Length - 1);
            } else {
                result.Append(currentChar);
            }
        }
        return result.ToString();
    }
    private void Reverse(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb[start];
            sb[start++] = sb[end];
            sb[end--] = temp;
        }
    }
}

C++ решение

auto-draft, проверить перед отправкой

#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 string ReverseParentheses(string s) {
        stack<int> openParenthesesIndices = new stack<int>();
        StringBuilder result = new StringBuilder();
        foreach (char currentChar in s) {
            if (currentChar == '(') {
                openParenthesesIndices.push(result.size());
            } else if (currentChar == ')') {
                int start = openParenthesesIndices.pop();
                Reverse(result, start, result.size() - 1);
            } else {
                result.Append(currentChar);
            }
        }
        return result.ToString();
    }
    private void Reverse(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb[start];
            sb[start++] = sb[end];
            sb[end--] = temp;
        }
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public String reverseParentheses(String s) {
        Stack<Integer> openParenthesesIndices = new Stack<>();
        StringBuilder result = new StringBuilder();

        for (char currentChar : s.toCharArray()) {
            if (currentChar == '(') {
                openParenthesesIndices.push(result.length());
            } else if (currentChar == ')') {
                int start = openParenthesesIndices.pop();
                reverse(result, start, result.length() - 1);
            } else {
                result.append(currentChar);
            }
        }

        return result.toString();
    }

    private void reverse(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start++, sb.charAt(end));
            sb.setCharAt(end--, temp);
        }
    }
}

JavaScript решение

сопоставлено/оригинал

var reverseParentheses = function(s) {
    let openParenthesesIndices = [];
    let result = [];

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            openParenthesesIndices.push(result.length);
        } else if (s[i] === ')') {
            let start = openParenthesesIndices.pop();
            reverse(result, start, result.length - 1);
        } else {
            result.push(s[i]);
        }
    }

    return result.join('');
};

function reverse(arr, start, end) {
    while (start < end) {
        [arr[start], arr[end]] = [arr[end], arr[start]];
        start++;
        end--;
    }
}

Python решение

сопоставлено/оригинал

class Solution:
    def reverseParentheses(self, s: str) -> str:
        openParenthesesIndices = []
        result = []

        for char in s:
            if char == '(':
                openParenthesesIndices.append(len(result))
            elif char == ')':
                start = openParenthesesIndices.pop()
                result[start:] = result[start:][::-1]
            else:
                result.append(char)

        return ''.join(result)

Go решение

сопоставлено/оригинал

func reverseParentheses(s string) string {
    var openParenthesesIndices []int
    result := []byte{}

    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            openParenthesesIndices = append(openParenthesesIndices, len(result))
        } else if s[i] == ')' {
            start := openParenthesesIndices[len(openParenthesesIndices)-1]
            openParenthesesIndices = openParenthesesIndices[:len(openParenthesesIndices)-1]
            reverse(result[start:])
        } else {
            result = append(result, s[i])
        }
    }

    return string(result)
}

func reverse(sb []byte) {
    for i, j := 0, len(sb)-1; i < j; i, j = i+1, j-1 {
        sb[i], sb[j] = sb[j], sb[i]
    }
}

Algorithm

Инициализируйте пустой стек openParenthesesIndices для отслеживания начальных точек разворота и пустую строку result для построения выходного результата.

Для каждого символа currentChar во входной строке:

Если это '(', добавьте длину строки result в openParenthesesIndices, чтобы отметить потенциальную начальную точку разворота.

Если это ')', извлеките значение из openParenthesesIndices и переверните result от извлеченного индекса для выполнения необходимого разворота.

В противном случае добавьте currentChar к result для построения строки.

Верните result как окончательную строку со всеми примененными разворотами.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.