와일드카드 문자 '?'를 대체하여 형성된 모든 균형 대괄호 문자열을 인쇄합니다.

균형 대괄호는 대괄호 문자열이 있는 경우 모든 여는 대괄호에 해당하는 닫는 대괄호가 있고 대괄호 쌍이 올바르게 중첩된다는 의미입니다. 문자열의 크기는 짝수여야 합니다. 이 문제에서는 문자 '?'를 포함하는 대괄호 문자열이 제공되며 우리의 임무는 '?'를 적절한 대괄호로 대체하여 가능한 모든 균형 대괄호 문자열을 구성하는 것입니다. 주어진 문자열에서는 괄호 '(' 및 ')'만 사용됩니다.

예제 예

으아아아

Explanation

의 중국어 번역은

Explanation

입니다.

'?'를 대체하여 균형 잡힌 문자열만 만들 수 있습니다.

으아아아 으아아아

Explanation

의 중국어 번역은

Explanation

입니다.

균형 잡힌 현을 만드는 방법에는 두 가지가 있습니다.

• 한 가지 방법은 인덱스 0, 1, 2를 여는 괄호로 바꾸고 다른 인덱스를 닫힌 괄호로 바꾸는 것입니다.

• 두 번째 방법은 인덱스 0, 1, 3을 여는 괄호로 바꾸고 나머지 인덱스를 닫힌 괄호로 바꾸는 것입니다.

• 세 번째 방법은 인덱스 0, 1, 4를 여는 괄호로 바꾸고 나머지 인덱스를 닫힌 괄호로 바꾸는 것입니다.

• 네 번째 방법은 인덱스 0, 2, 3의 위치를 ​​열린 괄호로 바꾸고 다른 인덱스 위치를 닫힌 괄호로 바꾸는 것입니다.

• 마지막 방법은 인덱스 0, 2, 4를 여는 괄호로 바꾸고 다른 인덱스를 닫힌 괄호로 바꾸는 것입니다.

방법

위에서 주어진 문자열의 예를 확인했습니다. 다음 단계로 넘어가겠습니다.

역추적 방법을 사용하여 이 문제를 해결할 수 있습니다.

이 방법에 대해 아래에서 논의하겠습니다 -

• 먼저 '?'를 대괄호로 바꾼 후 매개변수 str 및 index = 0을 사용하여 'create'라는 함수를 초기화합니다.

• 이 기능에서는

−> 먼저 기본 조건을 설정합니다. 문자열의 끝에 도달하면 문자열이 균형을 이루는지 확인하기 위해 문자열을 "check" 함수에 전달해야 합니다. 균형이 잡혀 있으면 문자열을 인쇄합니다.

−>문자열의 현재 문자가 '?'인 경우,

먼저 여는 괄호로 바꾸고 동일한 함수를 호출하여 문자열 끝에 도달했는지 확인합니다.

두 번째로, 닫는 괄호로 바꾸고 동일한 함수를 다시 호출하여 문자열 끝에 도달했는지 확인하세요.

마지막으로 문자열을 역추적하고 현재 문자를 '?'에 할당합니다

−> 그렇지 않고 문자열의 현재 문자가 대괄호이면 동일한 함수를 호출하여 다음 인덱스로 이동합니다.

• '검사' 기능을 초기화하여 문자열이 균형을 이루고 있는지 확인하세요.

−> 이 함수에서는 스택을 초기화한 다음

를 확인합니다.

−> 문자열의 첫 번째 문자가 닫는 괄호이면 false를 반환합니다

−> 현재 대괄호가 닫혀 있으면 두 가지 상황이 있습니다. 스택이 비어 있으면 해당 열림 대괄호가 없기 때문에 false가 반환됩니다. 그렇지 않으면 스택에서 해당 열린 괄호를 팝합니다.

−> 마지막으로 스택이 비어 있는지 확인합니다. 비어 있으면 문자열이 균형을 이루고 true를 반환한다는 의미입니다. 그렇지 않으면 문자열이 균형이 맞지 않고 false를 반환한다는 의미입니다.

Example

의 중국어 번역은 다음과 같습니다:

Example

다음은 균형 잡힌 모든 문자열을 얻기 위해 위의 역추적 방법에 사용된 C++ 코드입니다

으아아아

출력

으아아아

시간 복잡도와 공간 복잡도

위 코드의 시간 복잡도는 문자열을 역추적해야 하기 때문에 O(N*(2^N))입니다.

위 코드의 공간 복잡도는 대괄호를 스택에 저장하기 때문에 O(N)입니다.

여기서 N은 문자열의 크기입니다.

결론

이 튜토리얼에서는 와일드카드 문자 '?'를 대체하여 구성할 수 있는 모든 대괄호 문자열을 인쇄하는 프로그램을 구현했습니다. 역추적 방식을 구현했습니다. 시간 복잡도는 O(N*(2^N)이고 공간 복잡도는 O(N)입니다. 여기서 N은 문자열의 크기입니다.

위 내용은 와일드카드 문자 '?'를 대체하여 형성된 모든 균형 대괄호 문자열을 인쇄합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!