괄호 문자열이 유효한지 확인-PHP 튜토리얼-php.cn

괄호 문자열이 유효한지 확인

DDD

풀어 주다： 2025-01-12 22:04:47

원래의

520명이 탐색했습니다.

2116. 괄호 문자열이 유효한지 확인

난이도:중

주제: 문자열, 스택, 탐욕

괄호 문자열은 '(' 및 ')'로만 구성된 비어 있지 않은 문자열입니다. 다음 조건 중 하나라도 해당하면 유효합니다.

()입니다.
AB(A와 B를 연결)로 작성할 수 있습니다. 여기서 A와 B는 유효한 괄호 문자열입니다.
(A)로 작성할 수 있습니다. 여기서 A는 유효한 괄호 문자열입니다.

길이가 n인 괄호 문자열 s와 잠긴 문자열이 제공됩니다. 잠김은 '0'과 '1'로만 구성된 이진 문자열입니다. 잠긴 각 인덱스 i에 대해

locked[i]가 '1'이면 s[i]를 변경할 수 없습니다.
그러나 잠긴[i]가 '0'인 경우 s[i]를 '(' 또는 ')'로 변경할 수 있습니다.

s를 유효한 괄호 문자열로 만들 수 있으면 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

예 1:

괄호 문자열이 유효한지 확인

입력: s = "))()))", 잠김 = "010100"
출력: true
설명: 잠긴[1] == '1' 및 잠긴[3] == '1'이므로 s[1] 또는 s[3]을 변경할 수 없습니다.
- s[0]과 s[4]를 '('로 변경하고 s를 유효하게 만들기 위해 s[2]와 s[5]는 그대로 둡니다.

예 2:

입력: s = "()()", 잠김 = "0000"
출력: true
설명: s가 이미 유효하므로 변경할 필요가 없습니다.

예 3:

입력: s = ")", 잠김 = "0"
출력: false
설명: 잠김을 사용하면 s[0]을 변경할 수 있습니다.
- s[0]을 '(' 또는 ')'로 변경하면 s가 유효하지 않습니다.

제약조건:

n == s.length == 잠김.length
1 5
s[i]는 '(' 또는 ')'입니다.
잠긴[i]는 '0' 또는 '1'입니다.

힌트:

홀수 길이의 문자열이 유효할 수 있나요?
왼쪽에서 오른쪽으로 잠긴 ')'가 나타나면 왼쪽의 잠긴 '(' 또는 잠금 해제된 인덱스와 균형을 맞춰야 합니다. 둘 다 존재하지 않으면 어떤 결론을 내릴 수 있습니까? 둘 다 존재한다면, 어느 것을 사용하는 것이 더 바람직합니까?
위 이후에 '('의 잠긴 인덱스와 추가로 잠금 해제된 인덱스가 있을 수 있습니다. 이제 잠긴 '('의 균형을 어떻게 맞출 수 있습니까? 잠긴 '('의 균형을 맞출 수 없으면 어떻게 됩니까?

해결책:

잠긴 위치의 제약 조건과 동작을 염두에 두고 단계별로 접근할 수 있습니다.

핵심 포인트:

문자열의 길이가 홀수인 경우 유효한 괄호 문자열은 길이가 짝수여야 하기 때문에 즉시 false를 반환할 수 있습니다(각 열기(닫기 필요)).
문자열을 반복하면서 여는 괄호(() 및 닫는 괄호())의 수를 추적해야 합니다. 닫는 괄호의 수가 여는 괄호의 수를 초과하는 경우 문자열의 균형을 맞추는 것이 불가능하며 false를 반환합니다.
잠김(locked[i] == '1') 및 잠금 해제(locked[i] == '0') 위치를 신중하게 처리해야 합니다. 잠금 해제된 위치에서는 캐릭터를 변경할 수 있지만, 잠긴 위치에서는 변경할 수 없습니다.

연산:

1단계: 문자열 s의 길이가 홀수인지 확인하세요. 그렇다면 즉시 false를 반환하세요.
2단계: 문자열을 왼쪽에서 오른쪽으로 반복하여 괄호의 균형을 추적합니다.
- 카운터를 사용하여 괄호 열기(와 닫기) 사이의 균형을 추적하세요.
- 언제든지 닫는 괄호의 수가 여는 괄호의 수를 초과하는 경우 잠긴 위치에 균형을 맞출 수 있는 충분한 유연성이 있는지 확인하세요.
- 전체 문자열을 처리한 후 괄호가 균형을 이루고 있는지, 즉 일치하지 않는 여는 괄호가 남아 있지 않은지 확인하세요.

이 솔루션을 PHP로 구현해 보겠습니다: 2116. 괄호 문자열이 유효한지 확인

<?php /**
 * @param String $s
 * @param String $locked
 * @return Boolean
 */
function canBeValid($s, $locked) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$s = "))()))";
$locked = "010100";
var_dump(canBeValid($s, $locked));  // Output: bool(true)

$s = "()()";
$locked = "0000";
var_dump(canBeValid($s, $locked));  // Output: bool(true)

$s = ")";
$locked = "0";
var_dump(canBeValid($s, $locked));  // Output: bool(false)
?>

로그인 후 복사

설명:

첫 번째 패스(왼쪽에서 오른쪽으로):
- 문자열을 반복하고 여는 괄호의 균형을 추적합니다. 여는 괄호를 만날 때마다(열림 카운터를 증가시킵니다. 닫힌 괄호의 경우), 여는 카운터를 감소시킵니다.
- 현재 문자가 잠금 해제된 경우(locked[i] == '0'), 괄호의 균형을 맞추기 위해 필요한 경우 (라고 가정할 수 있습니다.
- 어느 지점에서든 열기 카운터가 음수가 되면 이는 여는 괄호보다 닫는 괄호가 더 많다는 의미이며 false를 반환합니다.
두 번째 패스(오른쪽에서 왼쪽으로):
- 문자열 끝에 있을 수 있는 일치하지 않는 여는 괄호의 시나리오를 처리하기 위해 유사한 작업을 역으로 수행합니다.
- 여기서는 닫기 카운터를 사용하여 닫는 괄호())를 추적하고 균형이 맞지 않는 괄호가 없는지 확인합니다.
예외 사례: 문자열 길이가 홀수인 경우 유효한 괄호 문자열을 구성할 수 없으므로 즉시 false를 반환합니다.