921. Minimum Add to Make Parentheses Valid

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

LeetCode Static

Строка со скобками допустима тогда и только тогда, когда: это пустая строка, ее можно записать как AB (A, совмещенное с B), где A и B - допустимые строки, или ее можно записать как (A), где A - допустимая строка. Вам дана строка s со скобками. За один ход вы можете вставить скобку в любую позицию строки. Например, если s = "()))", вы можете вставить открывающую скобку в виде "(()))" или закрывающую скобку в виде "())))". Верните минимальное количество ходов, необходимое для того, чтобы сделать s допустимой.

Пример:

Input: n = 3, goal = 3, k = 1

Output: 6

C# решение

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

public class Solution {
    public int MinAddToMakeValid(string s) {
        int openNeeded = 0;
        int closeNeeded = 0;
        
        foreach (char c in s) {
            if (c == '(') {
                openNeeded++;
            } else if (c == ')') {
                if (openNeeded > 0) {
                    openNeeded--;
                } else {
                    closeNeeded++;
                }
            }
        }
        
        return openNeeded + closeNeeded;
    }
}

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 int MinAddToMakeValid(string s) {
        int openNeeded = 0;
        int closeNeeded = 0;
        
        foreach (char c in s) {
            if (c == '(') {
                openNeeded++;
            } else if (c == ')') {
                if (openNeeded > 0) {
                    openNeeded--;
                } else {
                    closeNeeded++;
                }
            }
        }
        
        return openNeeded + closeNeeded;
    }
}

Java решение

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

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int MinAddToMakeValid(String s) {
        int openNeeded = 0;
        int closeNeeded = 0;
        
        foreach (char c in s) {
            if (c == '(') {
                openNeeded++;
            } else if (c == ')') {
                if (openNeeded > 0) {
                    openNeeded--;
                } else {
                    closeNeeded++;
                }
            }
        }
        
        return openNeeded + closeNeeded;
    }
}

JavaScript решение

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

var minAddToMakeValid = function(s) {
    let openNeeded = 0, closeNeeded = 0;
    
    for (const char of s) {
        if (char === '(') {
            openNeeded++;
        } else if (char === ')') {
            if (openNeeded > 0) {
                openNeeded--;
            } else {
                closeNeeded++;
            }
        }
    }
    
    return openNeeded + closeNeeded;
};

Python решение

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

def minAddToMakeValid(s: str) -> int:
    open_needed = close_needed = 0
    for char in s:
        if char == '(':
            open_needed += 1
        elif char == ')':
            if open_needed > 0:
                open_needed -= 1
            else:
                close_needed += 1
    return open_needed + close_needed

Go решение

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

package main

func minAddToMakeValid(s string) int {
    openNeeded := 0
    closeNeeded := 0
    
    for _, char := range s {
        if char == '(' {
            openNeeded++
        } else if char == ')' {
            if openNeeded > 0 {
                openNeeded--
            } else {
                closeNeeded++
            }
        }
    }
    
    return openNeeded + closeNeeded
}

Algorithm

Инициализировать два счетчика open_needed и close_needed.

Пройти по строке s символ за символом:

Если текущий символ - открывающая скобка (, увеличьте open_needed.

Если текущий символ - закрывающая скобка ), проверьте:

Если open_needed больше 0, уменьшите open_needed.

Иначе увеличьте close_needed.

Суммируйте значения open_needed и close_needed, чтобы получить минимальное количество вставок.

😎

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

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

Все вакансии

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