유효한 괄호를 만들기 위한 최소 제거 LeetCode 솔루션

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

또한 유효한 괄호를 만들기 위한 최소 제거 LeetCode 솔루션 - 당신은 문자열을 받았다 s '(', ')' 및 영문 소문자.

당신의 임무는 괄호의 최소 수( '(' 또는 ')', 임의의 위치에 있음)를 제거하여 결과가 괄호 문자열 유효하고 반환 어떤 유효한 문자열.

공식적으로, 괄호 문자열 다음과 같은 경우에만 유효합니다.

• 소문자만 포함하는 빈 문자열이거나
• A와 B가 유효한 문자열인 경우 AB(A와 B 연결)로 작성할 수 있습니다.
• (A)로 쓸 수 있습니다. 여기서 A는 유효한 문자열입니다.

예:핀

s = "lee(t(c)o)de)"

"lee(t(c)o)de"

설명 :

마지막 닫기를 제거할 수 있습니다. 문자열을 유효하게 만드는 괄호.

s = "))(("

""

설명 :

빈 문자열도 유효합니다.

접근:

우리는 "count"라는 변수를 유지할 것입니다. 여는 대괄호를 만나면 늘리고 닫는 대괄호를 만나면 줄입니다. "count"의 값이 음수가 될 때마다 우리는 그것을 취할 수 없습니다 닫는 괄호, 그래서 우리는 그것을 제거합니다.

그 후, 일치하는 닫는 괄호가 없기 때문에 끝에서 여는 괄호의 "카운트" 수를 제거합니다.

암호

유효한 괄호를 만들기 위한 최소 제거 C++ 솔루션:

#include <bits/stdc++.h>
using namespace std;
string minRemoveToMakeValid(string s)
{
    string temp;
    int cnt = 0;
    for (auto ele : s)
    {
        if (ele == '(')
        {
            cnt++;
        }
        else if (ele == ')')
        {
            cnt--;
        }
        if (cnt < 0)
        {
            cnt++;
        }
        else
        {
            temp += ele;
        }
    }
    string answer;
    int n = temp.length();
    for (int i = n - 1; i >= 0; i--)
    {
        if (temp[i] != '(' or cnt <= 0)
        {
            answer += temp[i];
        }
        else
        {
            cnt--;
        }
    }
    reverse(answer.begin(), answer.end());
    return answer;
}
int main()
{
    string s = "lee(t(c)o)de)";
    cout << minRemoveToMakeValid(s) << endl;
    return 0;
}

"lee(t(c)o)de"

유효한 괄호를 만들기 위한 최소 제거 Java 솔루션:

public class TutorialCup {
    public static String minRemoveToMakeValid(String s) {
        int n = s.length();
        StringBuilder temp = new StringBuilder();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                count++;
            } else if (s.charAt(i) == ')') {
                count--;
            }
            if (count < 0) {
                count++;
            } else {
                temp.append(s.charAt(i));
            }
        }
        n = temp.length();
        StringBuilder answer = new StringBuilder();
        for (int i = n - 1; i >= 0; i--) {
            if (temp.charAt(i) != '(' || count <= 0) {
                answer.append(temp.charAt(i));
            } else {
                count--;
            }
        }
        answer.reverse();
        return answer.toString();
    }

    public static void main(String[] args) {
        String s = "lee(t(c)o)de)";
        System.out.println(minRemoveToMakeValid(s));
    }
}

"lee(t(c)o)de"

복잡성 분석 유효한 괄호를 만들기 위한 최소 제거 LeetCode 솔루션:

시간 복잡성

위 코드의 시간 복잡성은 O (N) 문자열을 두 번만 탐색하기 때문입니다. 여기서 n은 입력 문자열의 길이입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (N) 우리는 새로운 문자열 생성을 사용하고 있기 때문입니다.

참조 : https://en.wikipedia.org/wiki/Bracket_matching