301. Remove Invalid Parentheses
LeetCode
hard
original: C#
#array
#csharp
#hard
#hash-table
#leetcode
#recursion
#string
#two-pointers
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
Дана cadena s, содержащая скобки и буквы. Удалите минимальное количество неверных скобок, чтобы сделать строку допустимой.
return список уникальных строк, которые являются допустимыми с минимальным количеством удалений. Вы можете вернуть ответ в любом порядке.
Ejemplo:
Input: s = "()())()"
Output: ["(())()","()()()"]
C# solución
coincidente/originalusing System;
using System.Collections.Generic;
using System.Text;
public class Solution {
private HashSet<string> validExpressions = new HashSet<string>();
private int minimumRemoved = int.MaxValue;
private void Reset() {
validExpressions.Clear();
minimumRemoved = int.MaxValue;
}
private void Recurse(string s, int index, int leftCount, int rightCount, StringBuilder expression, int removedCount) {
if (index == s.Length) {
if (leftCount == rightCount) {
if (removedCount <= minimumRemoved) {
string possibleAnswer = expression.ToString();
if (removedCount < minimumRemoved) {
validExpressions.Clear();
minimumRemoved = removedCount;
}
validExpressions.Add(possibleAnswer);
}
}
return;
}
char currentCharacter = s[index];
int length = expression.Length;
if (currentCharacter != '(' && currentCharacter != ')') {
expression.Append(currentCharacter);
Recurse(s, index + 1, leftCount, rightCount, expression, removedCount);
expression.Length = length;
} else {
Recurse(s, index + 1, leftCount, rightCount, expression, removedCount + 1);
expression.Append(currentCharacter);
if (currentCharacter == '(') {
Recurse(s, index + 1, leftCount + 1, rightCount, expression, removedCount);
} else if (rightCount < leftCount) {
Recurse(s, index + 1, leftCount, rightCount + 1, expression, removedCount);
}
expression.Length = length;
}
}
public IList<string> RemoveInvalidParentheses(string s) {
Reset();
Recurse(s, 0, 0, 0, new StringBuilder(), 0);
return new List<string>(validExpressions);
}C++ solución
borrador automático, revisar antes de enviar#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:
private HashSet<string> validExpressions = new HashSet<string>();
private int minimumRemoved = int.MaxValue;
private void Reset() {
validExpressions.Clear();
minimumRemoved = int.MaxValue;
}
private void Recurse(string s, int index, int leftCount, int rightCount, StringBuilder expression, int removedCount) {
if (index == s.size()) {
if (leftCount == rightCount) {
if (removedCount <= minimumRemoved) {
string possibleAnswer = expression.ToString();
if (removedCount < minimumRemoved) {
validExpressions.Clear();
minimumRemoved = removedCount;
}
validExpressions.push_back(possibleAnswer);
}
}
return;
}
char currentCharacter = s[index];
int length = expression.size();
if (currentCharacter != '(' && currentCharacter != ')') {
expression.Append(currentCharacter);
Recurse(s, index + 1, leftCount, rightCount, expression, removedCount);
expression.size() = length;
} else {
Recurse(s, index + 1, leftCount, rightCount, expression, removedCount + 1);
expression.Append(currentCharacter);
if (currentCharacter == '(') {
Recurse(s, index + 1, leftCount + 1, rightCount, expression, removedCount);
} else if (rightCount < leftCount) {
Recurse(s, index + 1, leftCount, rightCount + 1, expression, removedCount);
}
expression.size() = length;
}
}
public vector<string> RemoveInvalidParentheses(string s) {
Reset();
Recurse(s, 0, 0, 0, new StringBuilder(), 0);
return new List<string>(validExpressions);
}Java solución
coincidente/originalimport java.util.HashSet;
import java.util.Set;
class Solution {
private Set<String> validExpressions = new HashSet<>();
private int minimumRemoved = Integer.MAX_VALUE;
private void reset() {
validExpressions.clear();
minimumRemoved = Integer.MAX_VALUE;
}
private void recurse(String s, int index, int leftCount, int rightCount, StringBuilder expression, int removedCount) {
if (index == s.length()) {
if (leftCount == rightCount) {
if (removedCount <= minimumRemoved) {
String possibleAnswer = expression.toString();
if (removedCount < minimumRemoved) {
validExpressions.clear();
minimumRemoved = removedCount;
}
validExpressions.add(possibleAnswer);
}
}
return;
}
char currentCharacter = s.charAt(index);
int length = expression.length();
if (currentCharacter != '(' && currentCharacter != ')') {
expression.append(currentCharacter);
recurse(s, index + 1, leftCount, rightCount, expression, removedCount);
expression.deleteCharAt(length);
} else {
recurse(s, index + 1, leftCount, rightCount, expression, removedCount + 1);
expression.append(currentCharacter);
if (currentCharacter == '(') {
recurse(s, index + 1, leftCount + 1, rightCount, expression, removedCount);
} else if (rightCount < leftCount) {
recurse(s, index + 1, leftCount, rightCount + 1, expression, removedCount);
}
expression.deleteCharAt(length);
}
}
public List<String> removeInvalidParentheses(String s) {
reset();
recurse(s, 0, 0, 0, new StringBuilder(), 0);
return new ArrayList<>(validExpressions);
}JavaScript solución
coincidente/originalclass Solution {
constructor() {
this.validExpressions = new Set();
this.minimumRemoved = Number.MAX_SAFE_INTEGER;
}
reset() {
this.validExpressions.clear();
this.minimumRemoved = Number.MAX_SAFE_INTEGER;
}
recurse(s, index, leftCount, rightCount, expression, removedCount) {
if (index === s.length) {
if (leftCount === rightCount) {
if (removedCount <= this.minimumRemoved) {
const possibleAnswer = expression.join('');
if (removedCount < this.minimumRemoved) {
this.validExpressions.clear();
this.minimumRemoved = removedCount;
}
this.validExpressions.add(possibleAnswer);
}
}
return;
}
const currentCharacter = s[index];
const length = expression.length;
if (currentCharacter !== '(' && currentCharacter !== ')') {
expression.push(currentCharacter);
this.recurse(s, index + 1, leftCount, rightCount, expression, removedCount);
expression.pop();
} else {
this.recurse(s, index + 1, leftCount, rightCount, expression, removedCount + 1);
expression.push(currentCharacter);
if (currentCharacter === '(') {
this.recurse(s, index + 1, leftCount + 1, rightCount, expression, removedCount);
} else if (rightCount < leftCount) {
this.recurse(s, index + 1, leftCount, rightCount + 1, expression, removedCount);
}
expression.pop();
}
}
removeInvalidParentheses(s) {
this.reset();
this.recurse(s, 0, 0, 0, [], 0);
return Array.from(this.validExpressions);
}
}Python solución
coincidente/originalclass Solution:
def __init__(self):
self.valid_expressions = set()
self.minimum_removed = float('inf')
def reset(self):
self.valid_expressions.clear()
self.minimum_removed = float('inf')
def recurse(self, s, index, left_count, right_count, expression, removed_count):
if index == len(s):
if left_count == right_count:
if removed_count <= self.minimum_removed:
possible_answer = "".join(expression)
if removed_count < self.minimum_removed:
self.valid_expressions.clear()
self.minimum_removed = removed_count
self.valid_expressions.add(possible_answer)
return
current_character = s[index]
length = len(expression)
if current_character != '(' and current_character != ')':
expression.append(current_character)
self.recurse(s, index + 1, left_count, right_count, expression, removed_count)
expression.pop()
else:
self.recurse(s, index + 1, left_count, right_count, expression, removed_count + 1)
expression.append(current_character)
if current_character == '(':
self.recurse(s, index + 1, left_count + 1, right_count, expression, removed_count)
elif right_count < left_count:
self.recurse(s, index + 1, left_count, right_count + 1, expression, removed_count)
expression.pop()
def removeInvalidParentheses(self, s: str) -> [str]:
self.reset()
self.recurse(s, 0, 0, 0, [], 0)
return list(self.valid_expressions)Go solución
coincidente/originalpackage main
import (
"fmt"
)
type Solution struct {
validExpressions map[string]bool
minimumRemoved int
}
func (sol *Solution) reset() {
sol.validExpressions = make(map[string]bool)
sol.minimumRemoved = int(^uint(0) >> 1) // Max int value
}
func (sol *Solution) recurse(s string, index, leftCount, rightCount, removedCount int, expression []rune) {
if index == len(s) {
if leftCount == rightCount {
if removedCount <= sol.minimumRemoved {
possibleAnswer := string(expression)
if removedCount < sol.minimumRemoved {
sol.validExpressions = make(map[string]bool)
sol.minimumRemoved = removedCount
}
sol.validExpressions[possibleAnswer] = true
}
}
return
}
currentCharacter := rune(s[index])
length := len(expression)
if currentCharacter != '(' && currentCharacter != ')' {
sol.recurse(s, index+1, leftCount, rightCount, removedCount, append(expression, currentCharacter))
} else {
sol.recurse(s, index+1, leftCount, rightCount, removedCount+1, expression)
expression = append(expression, currentCharacter)
if currentCharacter == '(' {
sol.recurse(s, index+1, leftCount+1, rightCount, removedCount, expression)
} else if rightCount < leftCount {
sol.recurse(s, index+1, leftCount, rightCount+1, removedCount, expression)
}
expression = expression[:length]
}
}
func (sol *Solution) RemoveInvalidParentheses(s string) []string {
sol.reset()
sol.recurse(s, 0, 0, 0, 0, []rune{})
results := []string{}
for expr := range sol.validExpressions {
results = append(results, expr)
}
return results
}Algorithm
Инициализация:
Инициализируйте arreglo, который будет хранить все допустимые выражения.
Начните рекурсию с самой левой скобки в последовательности и двигайтесь вправо.
Определите состояние рекурсии переменной index, представляющей текущий обрабатываемый индекс в исходном выражении. Также используйте переменные left_count и right_count для отслеживания количества добавленных левых и правых скобок соответственно.
Обработка текущего символа:
Если текущий символ (S[i]) не является скобкой, добавьте его к окончательному решению для текущей рекурсии.
Если текущий символ является скобкой (S[i] == '(' или S[i] == ')'), у вас есть два варианта: либо отбросить этот символ как недопустимый, либо рассмотреть эту скобку как часть окончательного выражения.
Завершение рекурсии и проверка:
Когда все скобки в исходном выражении обработаны, проверьте, является ли текущее выражение допустимым, проверяя значения left_count и right_count (должны быть равны).
Если выражение допустимо, проверьте количество удалений (rem_count) и сравните его с минимальным количеством удалений, необходимых для получения допустимого выражения до сих пор.
Если текущее значение rem_count меньше, обновите глобальный минимум и добавьте новое выражение в arreglo допустимых выражений.
😎
Vacantes para esta tarea
Se muestran vacantes activas con etiquetas coincidentes.
Todavía no hay vacantes activas.