주어진 문자열을 구성하는 데 필요한 접두사와 접미사의 최소 개수

접두사는 지정된 문자열의 하위 문자열이며, 0번째 인덱스에서 시작하여 문자열 크기까지입니다. 마찬가지로 접미사는 문자열 크기에 대한 길이 1의 하위 문자열이며 마지막 인덱스에서 끝납니다. 두 개의 문자열이 제공되며 첫 번째 문자열은 두 번째 문자열의 접두사와 접미사를 원하는 만큼 사용하여 어떤 방식으로든 생성되어야 합니다. 주어진 메소드에서 주어진 문자열을 생성할 수 없으면 -1을 반환합니다.

예

으아악 으아악

Explanation

의 중국어 번역은

Explanation

입니다.

접두사 "points"와 접미사 "tutorial"을 사용할 수 있으며 이를 연결하면 첫 번째 문자열을 얻을 수 있습니다. 여기에는 두 개의 부분 문자열만 필요하며 이것이 우리의 대답 또는 출력입니다.

으아악 으아악

Explanation

의 중국어 번역은

Explanation

입니다.

두 번째 문자열의 주어진 접미사 또는 접두사에서 첫 번째 문자열을 가져올 수 없습니다.

방법

이 문제를 해결하기 위해 이미 발생한 인스턴스를 저장하여 해결하는 동적 프로그래밍 개념을 사용하겠습니다.

• 먼저 두 문자열을 매개변수로 사용하고 정수를 반환하는 함수를 만듭니다.

• 이 함수에서는 먼저 문자열의 길이를 가져오고 해시 세트와 임시 문자열을 만들어 접두사를 가져옵니다.

• 두 번째 문자열을 반복하여 모든 접두사를 가져와서 해시 세트에 저장합니다. 마찬가지로 문자열을 뒤에서 앞으로 순회하면 모든 접미사를 가져와서 해시 세트에 저장할 수 있습니다.

• 그런 다음 동적 프로그래밍의 결과를 저장하는 배열을 만들고 배열의 각 인덱스 위치에 -1을 저장합니다.

• 중첩된 for 루프를 사용하여 첫 번째 문자열을 청크로 분할하고 해시 맵의 모든 청크를 연결할 수 있는지 찾습니다.

• 필요한 하위 문자열 수를 줄이기 위해 최선을 다할 것입니다. 이것이 불가능할 경우 -1이 반환됩니다.

예

으아악

출력

으아악

시간과 공간의 복잡성

위 코드의 시간 복잡도는 우리가 얻는 모든 접미사의 복잡도가 높기 때문에 O(N^2)이지만, 문자열을 반전시키면 시간 복잡도를 줄일 수 있습니다. 또한 문자열을 해시 세트에 저장하여 시간 복잡도를 높이고 동적 프로그래밍을 위한 루프를 중첩합니다.

위 코드의 공간 복잡도는 모든 접미사와 접두사를 해시 맵에 저장하기 때문에 O(N^2)입니다.

결론

이 튜토리얼에서는 주어진 문자열의 접미사와 접두사에서 최소 하위 문자열 수를 찾아 다른 주어진 문자열을 만드는 코드를 구현했습니다. 불가능할 경우 -1을 인쇄합니다. 우리는 요소를 해시 세트에 저장한 다음 시간 및 공간 복잡도가 O(N^2)인 중첩 루프를 사용하여 동적 프로그래밍의 개념을 사용했습니다.

위 내용은 주어진 문자열을 구성하는 데 필요한 접두사와 접미사의 최소 개수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!