문자를 주어진 해당 기호로 대체하여 형성된 가능한 모든 문자열을 생성합니다.

가능한 모든 문자열을 생성한다는 것은 문자열의 특정 문자를 해당 기호로 대체하여 가능한 모든 문자열을 생성하는 것입니다. 우리는 크기가 "N"인 문자열 "s"와 크기가 "M"인 문자 쌍의 정렬되지 않은 맵 "mp"를 얻습니다. 여기서는 문자열 "s"의 mp[i][0]을 mp[i][1]로 대체하여 가능한 모든 문자열을 생성하도록 할 수 있습니다.

예제 예

으아아아

설명 − 위 예에서는 총 8개의 문자열이 생성되었습니다.

으아아아

Notes - 위 예시에서는 총 4개의 문자열이 생성되었습니다.

으아아아

설명 − 위 예에서는 총 2개의 문자열이 생성되었습니다.

방법

이 방법에서는 무차별 대입 개념을 사용하여 가능한 모든 조합을 찾습니다.

• 먼저 문자열, 현재 인덱스, 주어진 맵을 매개변수로 취하고 반환 유형은 void가 되는 함수를 만듭니다.

• 이 함수에서는 현재 인덱스가 문자열의 크기와 같다는 기본 조건을 정의한 다음 문자열을 인쇄하고 함수에서 반환합니다.

• 그렇지 않으면 두 가지 옵션이 있습니다. 하나는 현재 인덱스를 변경하지 않고 다음 인덱스로 이동하는 것입니다. 이는 항상 옵션입니다.

• 두 번째 선택은 현재 캐릭터에 대체 캐릭터가 있는 경우에만 가능합니다. 교체품이 있으면 교체품을 호출합니다.

• 이후 함수에서 돌아가면 필요한 모든 결과가 자동으로 생성됩니다.

이해를 돕기 위해 위 메서드의 코드를 살펴보겠습니다.

예

으아아아

출력

으아아아

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(N*2^N)입니다. 왜냐하면 N 요소에 대해 방금 역추적했기 때문입니다. 여기서 N은 문자열 's'의 크기입니다.

위 코드의 공간 복잡도는 O(N*N)입니다. 왜냐하면 문자열을 완전한 문자열로 보내고 동시에 N개의 문자열 복사본이 있을 수 있기 때문입니다.

역추적 알고리즘

이전 방법에서는 우리가 보낸 문자열에 포인터가 없어 공간을 많이 차지했습니다. 공간과 시간의 복잡성을 줄이기 위해 역추적(backtracking) 개념을 사용하겠습니다.

예

으아아아

출력

으아아아

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(N*2^N)입니다. 왜냐하면 N 요소에 대해 방금 역추적했기 때문입니다. 여기서 N은 문자열 's'의 크기입니다.

위 코드의 공간 복잡도는 O(N)입니다. 왜냐하면 문자열의 주소를 전송하고 최대 N개의 스택만 내려갈 것이기 때문입니다.

결론

이 튜토리얼에서는 문자를 주어진 기호로 대체하여 가능한 모든 문자열을 생성하는 프로그램을 구현했습니다. 여기서 역추적 방법을 살펴보았는데, 코드의 시간 복잡도는 O(N*2^N)입니다. 여기서 N은 문자열의 크기이고, 공간 복잡도는 시간 복잡도와 같습니다. 공간 복잡성을 줄이기 위해 역추적 프로세스를 구현했습니다.

위 내용은 문자를 주어진 해당 기호로 대체하여 형성된 가능한 모든 문자열을 생성합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!