문자열을 '정확'하게 만들려면 대괄호 문자열의 하위 문자열에서 모든 대괄호를 뒤집는 작업이 몇 번 필요합니까?

cs.stackexchange https://cs.stackexchange.com/questions/119847

  •  28-09-2020
  •  | 
  •  

문제

모든 여는 괄호가 그 뒤 어딘가에 해당하는 닫는 괄호가 있고 모든 닫는 괄호가 그 앞에 해당하는 여는 괄호가 있으면 나는 대괄호 문자열을 '올바른'이라고 부릅니다.예를 들어

(())()((()()))

올바른 문자열이고

)()()(

잘못된 문자열입니다.

작업은 입력 문자열의 인접한 하위 시퀀스를 취하고 해당 하위 시퀀스의 모든 괄호를 '뒤집는' 작업으로 구성됩니다.

임의의 괄호 문자열(길이가 짝수)이 주어지면 이를 '올바른' 괄호 문자열로 변경하는 데 필요한 이러한 작업의 가장 작은 수를 찾는 것이 임무입니다.

이 문제를 보는 또 다른 방법은 +1과 -1의 문자열을 갖고 이 문자열의 모든 접두어를 음수가 아닌 값으로 만드는 데 필요한 최소 연산 수(간격의 모든 숫자에 -1을 곱하는 것)를 찾는 것입니다. 모든 접미사는 양수가 아닙니다.

도움이 되었습니까?

해결책

DP는 Yuval Filmus의 의견을 제시했습니다. 실제로 작동합니다. $ \ mathcal {o} (n ^ {2}) $ 에서 문제를 해결할 수 있습니다. dp.

첫 번째 간격이 겹치지 않고 가정 해당 간격이 겹치지 않는다고 가정합니다. $ [a, b) $ 및 $ [C, D) $ 이라는 두 개의 겹치는 간격을 가져옵니다. WLOG $ a \ leq c $ . 그런 다음 두 개의 간격을 간격 $ [a, c) $ 및 $ [\ min (b, d) ), \ max (b, d)) $ 겹치지 않는 $ 총 길이가 짧아지고 동일한 요소를 정확하게 덮으십시오.

$ 1 $ , $-1 $ 을 사용하여 닫는 괄호로 열기 브래킷을 교체하십시오. 이제 문제는 $-1 $ "에 의한 "에 의한 최소 연산 수를 적용하고 전체 배열의 합계가 0.

왼쪽에서 오른쪽으로 해결책을 만듭니다. 모든 위치에서 간격을 시작하거나 활성 간격을 종료 할 수 있습니다.

$ DP [m] [0] $ 은 첫 번째 <스팬의 모든 접두사 합계를 사용해야하는 최소 간격 수를 나타냅니다. class="수학 컨테이너"> $ m $ 요소는 첫 번째 $ m $ 요소의 합계가 $ S $ 을 사용하면 활성 간격이 없습니다. 마찬가지로 $ dp [m] [1] $ 은 활성 간격이있는 값과 동일한 값입니다.

$ M $ th 값이 $ 1 $ 에 대해 $ 0 \ LEQ S \ LEQ M $ 우리는

를 설정합니다.

  • $ DP [M] [s] [0]= DP [M-1] [S-1] [0] $
  • $ DP [M] [s] [1]= DP [M-1] [s + 1] [1] $

그렇지 않으면

를 설정합니다.

  • $ DP [m] [s] [0]= DP [M-1] [s + 1] [0] $
  • $ DP [m] [s] [1]= DP [M-1] [S-1] [1] $ .

그런 다음 간격을 끝내고 간격을 시작하고

  • $ dp [m] [s] [0]=min (DP [m] [0], DP [m] [1]) $
  • $ dp [m] [s] [1]=min (DP [m] [1], DP [m] [0] + 1) $

기본 케이스는 $ dp [0] [0] [0]= 0 $ , $ dp [0 ] [0] [1]= 1 $ .

$ \ mathcal {o} (n ^ {2}) $ 상태가 있고, $ \ MathCal {o} (1) $ 작업을 계산하려면 알고리즘이 $ \ mathcal {o} (n ^ {2}) $ DP는 $ DP 값을 저장함으로써 $ \ mathcal {o} (n) $ 메모리를 사용하도록 구현할 수 있습니다. $ $ m $

여기에 알고리즘의 C ++ 구현이 있습니다. 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.size();

    vector<int> dp0 = {0}, dp1 = {1};
    for (int m = 1; m <= n; ++m) {
        vector<int> nxt0(m + 1, n + 1), nxt1(m + 1, n + 1);
        for (int i = 0; i < m; ++i) {
            if (str[m-1] == '(') {
                nxt0[i+1] = dp0[i];
                if (i > 0) nxt1[i-1] = dp1[i];
            } else {
                nxt1[i+1] = dp1[i]);
                if (i > 0) nxt0[i-1] = dp0[i];
            }
        }
        dp0 = nxt0;
        dp1 = nxt1;
        for (int i = 0; i <= m; ++i) dp1[i] = min(dp1[i], dp0[i] + 1); // Start interval
        for (int i = 0; i <= m; ++i) dp0[i] = min(dp0[i], dp1[i]); // Stop interval
    }
    cout << dp0[0] << '\n';
}
.

다른 팁

좋은 질문!

여기에 더 대중적인 용어로 문제가 있습니다.

균형 괄호

부분 문자열 "()"을 반복적으로 제거하여 빈 문자열로 변경할 수 있으면 괄호 문자열이 균형을 이룹니다.예를 들어, 빈 문자열 "()"과 "(())()((()()))"는 균형을 이루지만 "())"와 ")()()("는 균형을 이루지 않습니다.

균형 잡힌 문자열은 "("로 시작하고 ")"로 끝나야 한다는 것은 분명합니다.길이도 균일해야 합니다.

문자열의 균형을 맞추기 위한 최소 연산의 문제

허락하다 s 길이가 괄호로 이루어진 비어 있지 않은 문자열이어야 합니다. n.우리가 수행할 수 있는 유일한 작업은 하위 문자열의 모든 괄호를 뒤집는 것입니다. 즉, 문자열의 일부 연속 문자에 대해 모든 "("를 ")"로, 모든 ")"를 "("로 변경하는 것입니다.문제는 가장 적은 수의 연산을 찾는 방법입니다. s 균형이 잡힌.

동적 프로그래밍에 의한 접근 방식

적절한 하위 문제는 무엇입니까?그들은 dp[i][j] ~을 위한 0 <= i < j < n, 어디 dp[i][j] 인덱스 사이의 하위 문자열 균형을 유지하는 최소 작업 수입니다. i 및 색인 j 포함한.균형을 맞추는 원하는 최소 작업 수 s ~이다 dp[0][n-1].

홀수 길이의 문자열은 균형을 이룰 수 없으므로 이제부터는 짝수 길이의 문자열에만 주의를 기울이겠습니다.

기본 사례 dp[i][i+1] 사이의 하위 문자열이 있으면 0입니다. i 그리고 i+1 균형이 잡혀 있습니다(예: "()").그렇지 않으면 1입니다.

재발 관계순환 관계를 정의하기 위해 Java를 사용하겠습니다.

void dp(int i, int j) {
    assert 0 <=i && i + 2 < j && j <= L;

    int min = dp[i + 1][j - 1];
    if (s.charAt(i) == ')' && s.charAt(i + 1) == '(') min++;
    if (s.charAt(j) == '(' && s.charAt(j - 1) == ')') min++;

    for (int k = i + 1; k < j - 1; k+=2) {
        if (a[k] == 1 && a[k + 1] == -1) {
            if (min > dp[i][k] + dp[k + 1][j] - 1) {
                min = dp[i][k] + dp[k + 1][j] - 1;
            }
        } else {
            if (min > dp[i][k] + dp[k + 1][j]) {
                min = dp[i][k] + dp[k + 1][j];
            }
        }
    }

    dp[i][j] = min;
}

반복 관계는 균형 잡힌 문자열의 다음과 같은 잘 알려진 속성에서 비롯됩니다.비어 있지 않은 문자열은 두 균형 문자열의 연결이거나 "(" 뒤에 균형 문자열 뒤에 ")"가 오는 경우에만 균형이 맞습니다.

처리 전 for 루프, 설정 min 장차 ~ 가 되는 dp[i + 1][j - 1] 더하기 0, 1 또는 2는 "(" 다음에 균형 잡힌 문자열, ")"가 균형 있는 문자열이어야 한다는 사실에서 비롯됩니다.

에서 처리 for 축소를 시도하는 루프 min 에게 dp[i][k] + dp[k + 1][j] 일부의 경우 마이너스 0 또는 1 k 그건 사이에 있어 i 그리고 j, 두 균형 문자열의 연결은 균형 문자열이어야 한다는 사실에서 비롯됩니다.

이 접근 방식의 시간 복잡도는 다음과 같습니다. $O(n^3)$.공간복잡도는 $O(n^2)$.

"가장 불균형한" 현의 길이

2개 미만의 작업으로 균형을 맞출 수 없는 문자열의 최소 길이는 4입니다.예를 들어, ")((("

3회 미만의 연산으로 균형을 맞출 수 없는 문자열의 최소 길이는 10입니다.예를 들어, ")(((((())("

4개 미만의 연산으로 균형을 맞출 수 없는 문자열의 최소 길이는 22입니다.예를 들어, ")(())))(((((((((((())(".

질문:최소한 5번의 연산이 필요한 문자열의 가장 작은 길이는 얼마입니까?제가 계산한 대로 28보다 커야 합니다.그러나 내 계산으로는 실제 값을 결정하는 데 충분하지 않습니다.이러한 가장 작은 길이를 얼마나 빨리 계산할 수 있습니까?

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top