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

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'입니다.

힌트:

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

해결책:

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

핵심 포인트:

1. 문자열의 길이가 홀수인 경우 유효한 괄호 문자열은 길이가 짝수여야 하기 때문에 즉시 false를 반환할 수 있습니다(각 열기(닫기 필요)).
2. 문자열을 반복하면서 여는 괄호(() 및 닫는 괄호())의 수를 추적해야 합니다. 닫는 괄호의 수가 여는 괄호의 수를 초과하는 경우 문자열의 균형을 맞추는 것이 불가능하며 false를 반환합니다.
3. 잠김(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)
?>

설명:

1. 첫 번째 패스(왼쪽에서 오른쪽으로):

   • 문자열을 반복하고 여는 괄호의 균형을 추적합니다. 여는 괄호를 만날 때마다(열림 카운터를 증가시킵니다. 닫힌 괄호의 경우), 여는 카운터를 감소시킵니다.
   • 현재 문자가 잠금 해제된 경우(locked[i] == '0'), 괄호의 균형을 맞추기 위해 필요한 경우 (라고 가정할 수 있습니다.
   • 어느 지점에서든 열기 카운터가 음수가 되면 이는 여는 괄호보다 닫는 괄호가 더 많다는 의미이며 false를 반환합니다.

2. 두 번째 패스(오른쪽에서 왼쪽으로):

   • 문자열 끝에 있을 수 있는 일치하지 않는 여는 괄호의 시나리오를 처리하기 위해 유사한 작업을 역으로 수행합니다.
   • 여기서는 닫기 카운터를 사용하여 닫는 괄호())를 추적하고 균형이 맞지 않는 괄호가 없는지 확인합니다.

3. 예외 사례: 문자열 길이가 홀수인 경우 유효한 괄호 문자열을 구성할 수 없으므로 즉시 false를 반환합니다.

시간 복잡도:

• 두 패스(왼쪽에서 오른쪽 및 오른쪽에서 왼쪽)에는 선형 시간 O(n)이 소요됩니다. 여기서 n은 문자열 길이입니다. 따라서 전체 시간 복잡도는 O(n)이며 이는 입력 크기 제약 조건에 효율적입니다.

이 솔루션은 주어진 제약 내에서 문제를 올바르게 처리합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 괄호 문자열이 유효한지 확인의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!