주어진 배열에서 문자열 쌍의 첫 번째 문자를 교환하여 얻은 새 문자열 쌍의 수를 셉니다.

이 문제에서는 문자열 쌍을 선택하고 첫 번째 문자를 바꿔야 합니다. 그런 다음 새로운 쌍의 총 개수를 계산해야 합니다. 각 쌍의 첫 번째 문자를 바꾸고 해당 문자가 배열에 있는지 확인하면 이 문제를 해결할 수 있습니다.

이 문제를 해결하는 효율적인 방법은 해시 맵 데이터 구조를 사용하는 것입니다.

문제 설명 - N개의 문자열을 포함하는 배열이 있습니다. 모든 배열 요소에서 임의의 두 문자열을 선택하고 이 두 문자열의 첫 번째 문자를 바꿀 수 있습니다. 배열에는 없지만 생성된 새 문자열 쌍의 총 개수를 계산해야 합니다.

예제 예

입력 – array[] = {"should", "would", "can"};

출력 – 3

설명 – 새로 생성된 쌍은 could와 wan일 수 있습니다. 또 다른 쌍은 누구와 해야 하는지가 될 수 있습니다. 세 번째 쌍은 san과 chould일 수 있습니다.

입력 – array[] = {"demo", "test"};

출력 – 1

Explanation – 배열에 존재하지 않는 새로 생성된 쌍은 temo 및 dest입니다.

방법 1

이 방법에서는 두 개의 중첩 루프를 사용하여 모든 쌍의 배열 요소를 가져옵니다. 그런 다음 두 쌍의 첫 번째 문자를 교환합니다. 다음으로 세 번째 중첩 루프를 사용하여 배열에 해당 쌍이 포함되어 있는지 확인합니다.

알고리즘

• "cnt" 변수를 정의하고 0으로 초기화하여 총 쌍 수를 저장합니다.

• 두 개의 중첩 루프를 사용하여 문자열 배열을 반복하고 각 배열 요소 쌍을 가져옵니다.

• 두 문자열의 현재 쌍을 가져옵니다.

• 두 문자열의 첫 번째 문자가 같지 않으면 서로 바꿉니다.

• "isFirst" 및 "isSecond" 변수를 정의하고 false로 초기화하여 새로 생성된 문자열이 배열에 있는지 추적합니다.

• 세 번째 중첩 루프를 사용하여 배열에 새로 생성된 문자열이 있는지 확인하세요. 또한 isFirst 및 isSecond 변수의 값은 배열의 문자열을 기반으로 업데이트됩니다.

• 배열에 첫 번째 문자열과 두 번째 문자열이 모두 없으면 'cnt' 값을 1만큼 늘립니다.

• 'cnt' 변수의 값을 반환합니다.

예

으아아아

출력

으아아아

시간 복잡도 - O(N^3) 왜냐하면 세 개의 중첩 루프를 사용하기 때문입니다.

공간 복잡성 – O(1)

방법 2

이 방법에서는 지도 데이터 구조를 사용하여 모든 배열 값을 지도에 저장합니다. 그런 다음 지도에 새로 생성된 문자열이 포함되어 있는지 확인할 수 있습니다. 그렇지 않다면 개수를 1씩 늘릴 수 있습니다.

알고리즘

• 변수 'cnt' 정의

• 문자열 배열을 반복하고 모든 배열 값을 맵에 저장합니다.

• 두 개의 중첩 루프를 사용하여 모든 쌍의 배열 요소를 가져옵니다.

• 문자열 쌍을 가져와 "첫 번째" 및 "두 번째" 변수에 저장합니다.

• 두 문자열의 첫 번째 문자가 같지 않으면 서로 바꿉니다.

• 새로 생성된 문자열이 맵에 포함되어 있는지 확인하세요. 그렇지 않은 경우 "cnt" 값을 1만큼 늘립니다.

• 'cnt' 값을 반환합니다.

예

으아아아

출력

으아아아

시간 복잡도 - 두 개의 중첩 루프를 사용하기 때문에 O(N^2)입니다.

Space Complexity – O(N) 왜냐하면 맵을 사용하여 모든 배열 요소를 저장하기 때문입니다.

배열 요소의 첫 번째 문자를 바꿔서 새로 생성된 쌍의 총 개수를 알 수 있습니다. 시간 복잡도 측면에서 두 번째 방법에 대한 코드를 최적화했지만 공간 복잡도 측면에서는 첫 번째 코드가 더 좋습니다.

위 내용은 주어진 배열에서 문자열 쌍의 첫 번째 문자를 교환하여 얻은 새 문자열 쌍의 수를 셉니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!