이진 문자열에서 동일하지 않은 문자가 있는 인덱스의 문자 쌍을 교환하여 문자열이 회문 문자열을 형성할 수 있는지 확인합니다.

문제 설명

문자열 str과 이진 문자열 B가 있습니다. 두 문자열의 길이는 N과 같습니다. 문자열 B에서 동일하지 않은 문자를 포함하는 인덱스 쌍에서 해당 문자를 여러 번 교환하여 문자열 str을 회문 문자열로 만들 수 있는지 확인해야 합니다.

예제 예

들어가세요

으아아아

출력

으아아아

Explanation

의 중국어 번역은

Explanation

입니다.

B[1]과 B[2]가 동일하지 않기 때문에 str[1]과 str[2]를 바꿀 수 있습니다. 최종 문자열은 'ASA'일 수 있습니다.

들어가세요

으아아아

출력

으아아아

Explanation

의 중국어 번역은

Explanation

입니다.

문자열 B에는 동일하지 않은 문자가 포함되어 있지 않기 때문에 문자열 회문을 만들 수 없습니다.

들어가세요

으아아아

출력

으아아아

Explanation

의 중국어 번역은

Explanation

입니다.

문자 빈도 불일치로 인해 문자열 str을 회문으로 만들 수 없습니다.

방법 1

첫 번째 방법에서는 문자열 str의 모든 문자를 사용하여 회문 문자열을 만들 수 있는지 확인합니다. 그렇다면 문자열 B에서 동일하지 않은 문자를 포함하는 인덱스 쌍의 문자를 교환하고 문자열을 회문으로 만들 수 있는지 확인할 수 있습니다. 그렇지 않으면 false를 반환합니다.

알고리즘

• 1단계 - 유틸리티() 함수를 실행하고 주어진 조건에 따라 문자를 교환하여 문자 교환을 통해 문자열이 회문이 될 수 있는지 확인합니다.

• 2단계 - canBePalindromic() 함수를 정의하여 str 문자를 사용하여 회문 문자열을 구성할 수 있는지 확인합니다.

• 2.1단계 − 문자열 str의 각 문자와 해당 빈도를 저장하는 맵을 만듭니다. for 루프를 사용하여 문자열을 반복하고 문자 빈도를 계산합니다.

• 2.2단계 - 짝수 및 홀수 빈도의 문자 수를 셉니다.

• 2.3단계 - 문자열에 있는 고유 문자의 총 개수를 가져오려면 set을 사용하세요.

• 2.4단계 − 문자열 길이가 홀수이고 홀수 빈도의 문자가 하나만 포함되어 있으면 true를 반환합니다.

• 2.5단계 − 문자열 길이가 짝수이면 빈도가 짝수인 모든 문자와 홀수 빈도가 있는 0개의 문자가 true를 반환합니다.

• 2.6단계 − false를 반환합니다.

• 3단계 - 문자열이 회문이 될 수 없으면 false를 반환합니다.

• 4단계 - 문자열 B에 '1'과 '0'이 여러 개 포함되어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

예

으아아아

출력

으아아아

• 시간 복잡도 - O(NlogN), for 루프를 사용하여 문자열을 순회하고 set의 insert() 메서드에 (logN) 시간이 걸리기 때문입니다.

• Space Complexity - O(K), 여기서 K는 총 고유 문자 수입니다.

방법 2

이 방법에서는 맵을 사용하는 대신 배열을 사용하여 문자의 빈도를 저장합니다.

알고리즘

• 1단계 - 길이가 26인 'charFrequancy' 배열을 만들고 0으로 초기화합니다.

• 2단계 - 문자열 B에 있는 1과 0의 총 개수를 셉니다.

• 3단계 - 배열에 있는 각 문자의 빈도를 업데이트합니다.

• 4단계 - 문자열 길이가 짝수이고 홀수 빈도가 0이 아닌 경우 false를 반환합니다.

• 5단계 - 문자열 길이가 홀수이고 홀수 빈도가 1보다 큰 경우 false를 반환합니다.

• 6단계 - 문자열에 1과 0이 모두 있으면 true를 반환합니다.

• 7단계 - false를 반환합니다.

예

으아아아

출력

으아아아

• 시간 복잡도 - O(N) for 루프를 사용하여 문자열을 반복하기 때문입니다.

• 공간 복잡도 − O(1) 왜냐하면 항상 길이가 26인 배열을 사용하기 때문입니다.

결론

주어진 조건에 따라 문자를 교환하여 문자열이 회문이 될 수 있는지 확인하는 두 가지 방법을 배웠습니다. 첫 번째 방법은 컬렉션과 맵을 사용하는 반면, 두 번째 방법은 배열만 사용하여 데이터를 저장합니다. insert() 메서드는 컬렉션에 데이터를 삽입하는 데 O(logn) 시간이 걸리는 반면, 배열은 O(1) 시간만 걸리기 때문에 두 번째 방법이 첫 번째 방법보다 낫습니다.

위 내용은 이진 문자열에서 동일하지 않은 문자가 있는 인덱스의 문자 쌍을 교환하여 문자열이 회문 문자열을 형성할 수 있는지 확인합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!