주어진 크기의 이진 문자열 배열에 존재하지 않는 순열을 찾습니다.

이 문제에서는 배열에서 누락된 길이 N의 이진 문자열을 모두 찾아야 합니다. 길이가 N인 이진 문자열의 모든 순열을 찾고 배열에 존재하지 않는 순열을 확인하여 이 문제를 해결할 수 있습니다. 여기서는 이 문제를 해결하기 위한 반복 및 재귀적 방법을 살펴보겠습니다.

문제 설명 - 서로 다른 길이의 이진 문자열을 포함하는 길이 N의 배열 arr[]이 제공되었습니다. 배열에서 길이가 N인 누락된 이진 문자열을 모두 찾아야 합니다.

예제 예

입력 – arr = {"111", "001", "100", "110"}, N = 3

출력 – [000, 010, 011, 101]

설명 – 길이가 3인 이진 문자열은 8개 있습니다. 2의 3승은 8과 같기 때문입니다. 따라서 길이가 3인 누락된 4개의 이진 문자열을 인쇄합니다.

입력 – str = {'00', '10', '11'}, N = 2

출력 –['01']

설명 – 배열에 '01'이 누락되어 출력에 인쇄됩니다.

방법 1

여기에서는 반복 방법을 사용하여 길이 N의 가능한 모든 이진 문자열을 찾습니다. 그런 다음 문자열이 배열에 존재하는지 확인합니다. 존재하지 않으면 문자열을 인쇄합니다.

알고리즘

• 컬렉션을 정의하고 insert() 메서드를 사용하여 배열의 모든 문자열을 컬렉션에 추가합니다.

• total 변수를 2N으로 초기화합니다. 여기서 2N은 길이가 N인 문자열의 총 개수입니다

• 'cnt' 변수를 정의하고 0으로 초기화하여 누락된 총 조합 수를 저장합니다.

• 루프를 사용하여 '총' 반복 횟수를 만들어 길이가 N인 모든 이진 문자열을 찾습니다.

• 루프에서 "num" 문자열 변수를 빈 문자열로 초기화합니다.

• 총 N회 반복에 중첩 루프를 사용하고 마지막 반복부터 시작하여 길이가 N인 문자열을 만듭니다.

• find() 메서드를 사용하여 컬렉션에 현재 문자열이 포함되어 있는지 확인하세요. 그렇다면 'cnt'의 값을 1만큼 늘립니다.

• 문자열이 맵에 없으면 인쇄하여 출력에 표시하세요

• "cnt"의 값이 전체 개수와 같다면, 배열에 길이 N의 문자열이 모두 존재한다는 의미이며, "-1"이 출력됩니다.

예

출력

시간 복잡도 - O(N*2N), 여기서 O(N)은 문자열이 배열에 존재하는지 확인하는 데 사용되고 O(2N)은 가능한 모든 순열을 찾는 데 사용됩니다.

공간 복잡도 - O(N). 왜냐하면 문자열을 저장하기 위해 set을 사용하기 때문입니다.

방법 2

이 방법에서는 재귀 방법을 사용하여 길이 N의 가능한 모든 이진 문자열을 찾는 방법을 보여줍니다.

알고리즘

• 컬렉션을 정의하고 모든 배열 값을 컬렉션에 삽입합니다.

• generateCombinations() 함수를 호출하여 모든 바이너리 문자열 조합을 생성하세요

• generateCombinations() 함수에서 기본 사례를 정의하세요. 인덱스가 N과 같으면 currentCombination이 목록에 추가됩니다.

• 현재 조합에 '0' 또는 '1'을 추가한 후 generateCombinations() 함수를 재귀적으로 호출하세요.

• 모든 조합을 얻은 후 배열에 어떤 조합이 있고 어떤 조합이 없는지 확인하세요. 또한 출력에 표시할 누락된 조합을 인쇄합니다.

예

출력

시간 복잡도 - O(N*2N)

공간 복잡도 - 모든 조합을 배열에 저장하므로 O(2N)입니다.

두 가지 방법 모두 동일한 논리를 사용하여 문제를 해결합니다. 첫 번째 방법은 반복 기법을 사용하여 길이가 N인 이진 문자열의 모든 조합을 찾는데, 이는 두 번째 방법에 사용된 재귀 기법보다 빠릅니다. 또한 두 번째 방법은 첫 번째 방법보다 더 많은 공간을 소비합니다.

위 내용은 주어진 크기의 이진 문자열 배열에 존재하지 않는 순열을 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!