Решение: минимум удалить, чтобы сделать действительные скобки

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашли его полезным, Пожалуйста, нравится Этот пост и/или upvote Мое решение по сообщению на форумах LeetCode Анкет

Проблема LeetCode #1249 (Medium): минимальный удаление, чтобы сделать действительные скобки

Описание:

Учитывая строку s из ‘(‘ , ‘)’ и строчные английские персонажи.

Ваша задача – удалить минимальное количество скобок ( ‘(‘ или ‘)’ , в любых позициях) так, чтобы результирующая строка скобок действителен и возвращает Любые Допустимая строка.

Формально, строка скобок действителен, если и только тогда, когда:

• Это пустая строка, содержит только строчные символы или
• Это может быть написано как Ab ( a Согласован с b ), где A и B действительные строки, или
• Это может быть написано как (А) В где A является действительной строкой.

Примеры:

Ограничения:

• 1.length^5
• s [i] один из '(' , ')' и строчные английские буквы.

Идея:

Действительные скобки следуют за LIFO Метод (Последнее, сначала), поэтому мы должны автоматически думать о каком -то виде стек решение.

Чтобы проверить действительные скобки, вы толкаете любые “(“ на стек , затем откачивать элемент верхнего стека каждый раз, когда вы найдете совпадение “)” . Если вы найдете “)” Когда стек пусто, это “)” Должно быть недействительным. В конце S , любой остаток “(“ остается в стек также должен быть недействительным. Так как мы захотим удалить их “(“ ‘s index в конце, стек должен содержать указанные индексы, а не просто “(“ .

Теперь, когда мы определили все неверные скобки, это оставляет нам проблему удаления их из S . Мы могли бы выполнить множество строк и копий, но они, как правило, очень медленные и интенсивные памяти, поэтому мы, вероятно, должны найти тип данных, который может быть непосредственно изменен путем доступа к индексу и использовать его в качестве посредника.

Наиболее эффективный метод варьируется в зависимости от языка, поэтому я буду обсуждать их в Реализация раздел.

Тогда мы можем сделать наши удаления и повторно формировать и возврат наш ответ.

Реализация:

У JavaScript есть основные массивы, у Python есть списки, а у Java есть массивы Char, которые выполнят работу более гибкого типа данных для этой проблемы. В одном только C ++ из четырех языков есть изменяемые строки, поэтому мы можем просто оставить S как есть.

В то время как у Java есть структуры Stack/Deque/List, они не всегда ужасно эффективны, поэтому мы можем просто использовать более базовый int [] с длиной, прикрепленной к размеру S , вместе с переменной индекса ( stix ).

JavaScript удобно позволяет нам напрямую удалять элемент массива, не обладая нашей итерацией, поэтому мы можем использовать его на начальном проходе для Invalid «(“ ‘s. Python не может этого сделать, но мы можем легко заменить каждого символа, который мы хотим удалить пустой строкой, которая эффективно делает то же самое, как только строка снова присоединилась.

Java и C ++ не позволят нам заменить символов пустыми строками, поэтому мы можем просто отметить этих символов Маска персонажа для последующего удаления.

На втором проходе через JavaScript и Python может просто повторить тот же метод, проходя через оставшиеся стек Анкет Python очень быстр со своими добавлениями и всплесками, поэтому мы можем использовать это в наших интересах.

Для Java и C ++ все сложнее. Мы не можем изменить длину посредника, но мы может изменить его содержимое с помощью указания индекса. Это означает, что мы можем использовать двухточечный подход для переписывания начальной части посредника, прежде чем в конечном итоге вернуть его подраздел.

Поскольку мы хотим итерации через стек В противоположном порядке ( fifo ) На этот раз мы можем просто пометить -1 на конце стека, чтобы избежать проблем с выходом из-за перехода, а затем используйте Stix Начиная с 0 Анкет

Тогда для каждой итерации, J увеличит, но я Будет увеличить только в том случае, если это не тот персонаж, который мы хотим удалить (либо сопоставляя маску символов, либо следующую запись стека), и мы перезаписываем посредника в я с J Значение.

В конце подвеска между 0 и я Будет представлять строку «сжимая» со всеми неверными снятыми скобками, поэтому мы должны возврат Это.

Код JavaScript:

var minRemoveToMakeValid = function(S) {
    S = S.split("")
    let len = S.length, stack = []
    for (let i = 0, c = S[0]; i < len; c = S[++i])
        if (c === ")")
            if (stack.length) stack.pop()
            else delete S[i]
        else if (c === "(") stack.push(i)
    for (let i = 0; i < stack.length; i++)
        delete S[stack[i]]
    return S.join("")
};

Код Python:

class Solution:
    def minRemoveToMakeValid(self, S: str) -> str:
        S, stack = list(S), []
        for i, c in enumerate(S):
            if c == ")":
                if stack: stack.pop()
                else: S[i] = ""
            elif c == "(": stack.append(i)
        for i in stack: S[i] = ""
        return "".join(S)

Код Java:

class Solution {
    public String minRemoveToMakeValid(String S) {
        char[] ans = S.toCharArray();
        int len = S.length(), stIx = 0, i = 0, j = 0;
        int[] stack = new int[len+1];
        for (; i < len; i++)
            if (ans[i] == ')')
                if (stIx > 0) stIx--;
                else ans[i] = '_';
            else if (ans[i] == '(') stack[stIx++] = i;
        for (i = 0, stack[stIx] = -1, stIx = 0; j < len; j++)
            if (j == stack[stIx]) stIx++;
            else if (ans[j] != '_') ans[i++] = ans[j];
        return new String(ans, 0, i);
    }
}

C ++ Код:

class Solution {
public:
    string minRemoveToMakeValid(string S) {
        int len = S.size(), i = 0, j = 0, stIx = 0;
        vector stack;
        for (; i < len; i++)
            if (S[i] == ')')
                if (stack.size() > 0) stack.pop_back();
                else S[i] = '_';
            else if (S[i] == '(') stack.push_back(i);
        stack.push_back(-1);
        for (i = 0; j < len; j++)
            if (j == stack[stIx]) stIx++;
            else if (S[j] != '_') S[i++] = S[j];
        return S.substr(0, i);
    }
};

Оригинал: “https://dev.to/seanpgallivan/solution-minimum-remove-to-make-valid-parentheses-2bdj”