회문을 형성하는 최소 삽입 수를 찾는 JavaScript 프로그램

문자열이 주어지면 최종 문자열이 회문이 되도록 주어진 문자열의 임의 위치에 삽입해야 하는 서로 다른 문자의 최소 수를 찾아야 합니다. 회문은 그 반대의 문자열과 정확히 동일한 문자열입니다. 이 질문은 동적으로 프로그래밍되어 있으므로 먼저 재귀적 방법을 사용한 다음 암기하고 마지막으로 암송 방법에 대한 표를 살펴보겠습니다.

재귀적 방법

예

으아악

출력

으아악

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(2^N)입니다. 삽입할 때마다 선택을 하기 때문입니다. 여기서 N은 주어진 문자열의 크기입니다.

위 코드의 공간 복잡도는 재귀 호출의 경우 O(N)입니다.

메모리 방식

예

으아악

출력

으아악

시간과 공간의 복잡성

위 코드의 시간복잡도는 계산된 결과를 저장하기 때문에 O(N^2)입니다.

위 코드의 공간 복잡도는 여기서 추가 공간을 사용하기 때문에 O(N^2)입니다.

동적 프로그래밍 방법

예

으아악

출력

으아악

시간과 공간의 복잡성

여기서는 중첩된 for 루프를 사용하고 있기 때문에 위 코드의 시간 복잡도는 O(N^2)입니다.

위 코드의 공간 복잡도는 여기서 추가 공간을 사용하기 때문에 O(N^2)입니다.

결론

이 튜토리얼에서는 주어진 문자열을 회문으로 만드는 데 필요한 최소 삽입 횟수를 찾기 위해 JavaScript 프로그래밍 언어를 사용하여 재귀부터 메모, 표 작성까지 세 가지 방법을 구현했습니다. 회문은 그 반대 부분과 정확히 동일한 문자열입니다. 또는 동일한 문자를 앞이나 뒤에서 읽을 수 있습니다.

위 내용은 회문을 형성하는 최소 삽입 수를 찾는 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!