문자열 사이의 문자를 원하는 만큼 대체하여 주어진 문자열을 T로 변환합니다.

문자열을 변환한다는 것은 주어진 조건에 따라 주어진 문자열과 동일하게 만들어야 함을 의미합니다. 이 질문에서는 문자열 "arr"과 크기 "M"의 문자열 "T"로 구성된 배열이 제공됩니다. 우리의 임무는 배열의 문자열( arr[i] )에서 문자를 제거하고 해당 문자를 다른 문자열의 인덱스에 삽입하여 배열에 있는 모든 문자열이 주어진 문자열과 동일하게 만들어질 수 있는지 확인하는 것입니다. 동일한 배열( arr[j] ). 우리는 이것을 원하는 만큼 여러 번 할 수 있습니다. 배열의 모든 문자열을 문자열 'T'와 동일하게 만들 수 있으면 "YES"를 반환하고, 그렇지 않으면 "NO"를 반환합니다.

예

으아악 으아악

지침

배열의 모든 문자열을 문자열 T와 동일하게 만드는 방법 중 하나는 다음과 같습니다.

• 인덱스 2의 문자열 arr[1]("wxxy")에서 문자를 삭제하고 인덱스 1의 문자열 arr[2]("wyzz")에 삽입합니다. 그러면 다음과 같습니다: ["wxyz","wxy","wxyzz"]

• 인덱스 3의 문자열 arr[2]("wxyzz")에서 문자를 삭제하고 이를 인덱스 3의 문자열 arr[1]("wxy")에 삽입합니다. 그러면 다음과 같습니다: ["wxyz","wxyz","wxyz"].

위 단계를 수행한 후 배열의 모든 문자열을 문자열 T와 동일하게 만들 수 있습니다. 그래서 대답은 "예"입니다.

으아악 으아악

지침

배열에는 3개의 문자열이 있는데, 그 중 2개는 문자열 T와 동일하지만 인덱스 번호 1의 문자열은 다릅니다. 문자열 T의 일부가 아닌 다른 문자가 포함되어 있습니다. 배열의 모든 문자열을 문자열 T로 만드는 것은 불가능합니다. 그러므로 대답은 "NO"이다.

방법: 해시맵 사용

위에서 주어진 문자열의 예를 확인했습니다. 메소드로 이동하겠습니다.

다음과 같이 두 가지 관찰 결과가 있습니다. -

• 배열의 모든 문자열을 문자열 T와 동일하게 만들어야 하기 때문에 배열에 있는 각 문자열의 모든 문자가 문자열 T에 나타나야 합니다. 즉, 다른 문자가 없습니다. 그렇지 않으면 조건을 충족할 수 없습니다.

• 배열의 모든 문자열에 대한 문자 발생 빈도를 계산한 후 각 문자의 발생 빈도는 배열 "N"의 크기와 같아야 합니다.

위의 관찰을 바탕으로 확인해야 할 두 가지 조건이 있습니다.

• 크기 배열 "freqArr"의 문자열 해시 맵은 문자열 "T"의 해시 맵 "freqT"와 같습니다.

으로

으아악

• 문자열 T의 모든 문자는 배열의 모든 문자열에 나타나야 합니다. 문자열 T의 각 문자는 배열 문자열에서 "N"의 빈도 수를 가져야 합니다. 그대로-

으아악

배열 문자열과 문자열 T에서 문자의 빈도를 계산해야 하기 때문에 해싱을 사용하여 이 문제를 해결할 수 있습니다.

예

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

으아악

출력

으아악

시간과 공간의 복잡성

위 코드의 시간복잡도는 O(M + N*L)

위 코드의 공간복잡도는 O(M)

여기서 M은 문자열 T의 크기이고, N은 배열의 크기이며, L은 배열에 존재하는 가장 긴 문자열입니다.

결론

이 튜토리얼에서는 문자열 사이의 문자를 필요한 만큼 바꿔서 주어진 문자열을 T로 변환하는 프로그램을 구현했습니다. 빈도를 저장해야 했기 때문에 해싱 방법을 구현했습니다. 이 방법에서는 주로 두 가지 조건을 확인하는데, 모든 조건이 충족되면 배열의 모든 문자열을 문자열 T와 동일한 문자열로 변환할 수 있다는 의미입니다.

위 내용은 문자열 사이의 문자를 원하는 만큼 대체하여 주어진 문자열을 T로 변환합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!