찾다
백엔드 개발PHP 튜토리얼괄호 문자열이 유효한지 확인

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
PHP 로깅 : PHP 로그 분석을위한 모범 사례PHP 로깅 : PHP 로그 분석을위한 모범 사례Mar 10, 2025 pm 02:32 PM

PHP 로깅은 웹 애플리케이션을 모니터링하고 디버깅하고 중요한 이벤트, 오류 및 런타임 동작을 캡처하는 데 필수적입니다. 시스템 성능에 대한 귀중한 통찰력을 제공하고 문제를 식별하며 더 빠른 문제 해결을 지원합니다.

Laravel의 플래시 세션 데이터로 작업합니다Laravel의 플래시 세션 데이터로 작업합니다Mar 12, 2025 pm 05:08 PM

Laravel은 직관적 인 플래시 방법을 사용하여 임시 세션 데이터 처리를 단순화합니다. 응용 프로그램에 간단한 메시지, 경고 또는 알림을 표시하는 데 적합합니다. 데이터는 기본적으로 후속 요청에만 지속됩니다. $ 요청-

PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법Mar 14, 2025 am 11:42 AM

PHP 클라이언트 URL (CURL) 확장자는 개발자를위한 강력한 도구이며 원격 서버 및 REST API와의 원활한 상호 작용을 가능하게합니다. PHP CURL은 존경받는 다중 프로모토콜 파일 전송 라이브러리 인 Libcurl을 활용하여 효율적인 execu를 용이하게합니다.

Laravel 테스트에서 단순화 된 HTTP 응답 조롱Laravel 테스트에서 단순화 된 HTTP 응답 조롱Mar 12, 2025 pm 05:09 PM

Laravel은 간결한 HTTP 응답 시뮬레이션 구문을 제공하여 HTTP 상호 작용 테스트를 단순화합니다. 이 접근법은 테스트 시뮬레이션을보다 직관적으로 만들면서 코드 중복성을 크게 줄입니다. 기본 구현은 다양한 응답 유형 단축키를 제공합니다. Illuminate \ support \ Facades \ http를 사용하십시오. http :: 가짜 ([ 'google.com'=> ​​'Hello World', 'github.com'=> ​​[ 'foo'=> 'bar'], 'forge.laravel.com'=>

Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트Mar 13, 2025 pm 12:08 PM

고객의 가장 긴급한 문제에 실시간 인스턴트 솔루션을 제공하고 싶습니까? 라이브 채팅을 통해 고객과 실시간 대화를 나누고 문제를 즉시 해결할 수 있습니다. 그것은 당신이 당신의 관습에 더 빠른 서비스를 제공 할 수 있도록합니다.

PHP에서 늦은 정적 결합의 개념을 설명하십시오.PHP에서 늦은 정적 결합의 개념을 설명하십시오.Mar 21, 2025 pm 01:33 PM

기사는 PHP 5.3에 도입 된 PHP의 LSB (Late STATIC BING)에 대해 논의하여 정적 방법의 런타임 해상도가보다 유연한 상속을 요구할 수있게한다. LSB의 실제 응용 프로그램 및 잠재적 성능

프레임 워크 사용자 정의/확장 : 사용자 정의 기능을 추가하는 방법.프레임 워크 사용자 정의/확장 : 사용자 정의 기능을 추가하는 방법.Mar 28, 2025 pm 05:12 PM

이 기사에서는 프레임 워크에 사용자 정의 기능 추가, 아키텍처 이해, 확장 지점 식별 및 통합 및 디버깅을위한 모범 사례에 중점을 둡니다.

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

뜨거운 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

PhpStorm 맥 버전

PhpStorm 맥 버전

최신(2018.2.1) 전문 PHP 통합 개발 도구

Atom Editor Mac 버전 다운로드

Atom Editor Mac 버전 다운로드

가장 인기 있는 오픈 소스 편집기

mPDF

mPDF

mPDF는 UTF-8로 인코딩된 HTML에서 PDF 파일을 생성할 수 있는 PHP 라이브러리입니다. 원저자인 Ian Back은 자신의 웹 사이트에서 "즉시" PDF 파일을 출력하고 다양한 언어를 처리하기 위해 mPDF를 작성했습니다. HTML2FPDF와 같은 원본 스크립트보다 유니코드 글꼴을 사용할 때 속도가 느리고 더 큰 파일을 생성하지만 CSS 스타일 등을 지원하고 많은 개선 사항이 있습니다. RTL(아랍어, 히브리어), CJK(중국어, 일본어, 한국어)를 포함한 거의 모든 언어를 지원합니다. 중첩된 블록 수준 요소(예: P, DIV)를 지원합니다.

Dreamweaver Mac版

Dreamweaver Mac版

시각적 웹 개발 도구