문자열 B를 얻기 위해 문자열 A를 추가하는 데 필요한 최소 하위 시퀀스를 추가합니다.

이 문제에서는 str1의 하위 시퀀스를 사용하여 str2를 구성해야 합니다. 이 문제를 해결하기 위해 최대 길이가 str2인 하위 문자열을 포함하는 str1의 하위 시퀀스를 찾을 수 있습니다. 여기서 우리는 문제를 해결하는 두 가지 다른 방법을 배울 것입니다.

문제 설명– 길이가 다른 두 개의 문자열, str1과 str2가 제공됩니다. 다음 조건에 따라 str1에서 str2를 구성해야 합니다.

• str1에서 하위 시퀀스를 선택하여 새 문자열(처음에는 비어 있음)에 추가합니다.

str2를 구성하는 데 필요한 최소 피연산자 수를 반환해야 하며, str2를 구성할 수 없으면 -1을 인쇄해야 합니다.

예

Enter – str1 = "acd", str2 = "adc"

출력– 2

지침

• str1의 첫 번째 하위 시퀀스는 "ad"입니다. 따라서 우리 문자열은 "ad"일 수 있습니다.

• 그런 다음 str1에서 "c" 하위 시퀀스를 가져와 "ad"에 추가하여 "adc"로 만들 수 있습니다.

Input– str1 = "adcb", str2 = "abdca"

출력–3

지침

• str1의 첫 번째 하위 시퀀스는 "ab"입니다.

• 이후에는 "dc" 문자열을 얻을 수 있고 결과 문자열은 "abdc"가 됩니다

• 다음으로 "a" 하위 시퀀스를 사용하여 최종 문자열 "abdca"를 생성할 수 있습니다.

방법 1

이 방법에서는 str1을 반복하여 여러 하위 시퀀스를 찾아 결과 문자열에 추가합니다.

알고리즘

• 길이가 26인 "arr" 배열을 정의하고 모든 요소를 ​​0으로 초기화하여 문자의 존재 여부를 str1에 저장합니다.

• str1을 반복하고 문자의 ASCII 값에 따라 배열 요소의 값을 업데이트합니다

• "마지막" 변수를 정의하고 -1로 초기화하여 마지막으로 방문한 요소를 추적합니다. 또한 "cnt" 변수를 정의하고 0으로 초기화하여 작업 횟수를 저장합니다.

• 루프를 사용하여 str2를 순회하세요.

• 현재 문자가 str1에 없으면 -1을 반환합니다.

• "j" 변수를 "last + 1" 값으로 초기화합니다.

• while 루프를 사용하여 j 값이 len보다 작고 str1[j]가 문자와 같지 않을 때까지 반복합니다.

• 'j' 값이 'len'보다 크면 'str1'을 반복합니다. 'cnt' 변수의 값을 늘리고, 'str1'을 다시 반복해야 하기 때문에 'last'를 -1로 초기화하고, 현재 문자를 다시 고려해야 하기 때문에 'I'의 값을 1만큼 줄입니다. '계속' 키워드 반복.

• "마지막" 변수의 값을 "j"로 업데이트하세요.

• 루프의 모든 반복이 완료된 후 "cnt + 1"을 반환합니다. 여기서는 마지막 작업을 고려하지 않기 때문에 "cnt"에 "1"을 추가해야 합니다.

예

으아악

출력

으아악

시간 복잡도 – O(N*M), 여기서 N은 str2의 길이이고 M은 str1의 길이입니다.

공간 복잡도 - 동적 공간을 사용하지 않으므로 O(1)입니다.

방법 2

이 방법에서는 위 방법의 효율성을 높이기 위해 매핑 및 수집 데이터 구조를 사용합니다. 문제를 해결하는 논리는 위와 같습니다.

알고리즘

• chars를 저장하려면 "chars_mp"를 정의하고{} 키-값 쌍으로 설정하세요.

• str1 문자열에 특정 문자가 존재하는 인덱스 집합을 맵에 저장합니다

• "last" 및 "cnt" 변수 정의

• str2 탐색을 시작합니다. 현재 문자 인덱스를 포함하는 컬렉션의 크기가 0이면 -1이 반환됩니다.

• 현재 문자 인덱스 세트에서 "마지막"의 상한을 찾아보세요.

• 상한값을 찾지 못한 경우 "cnt" 값을 1 증가시키고, "last" 값을 -1로 설정하고, "I" 값을 1 감소시킨 후 continue 키워드를 사용하세요. p>

• "마지막" 변수의 값을 업데이트하세요.

• 루프 반복이 완료된 후 'cnt' 변수의 값을 반환합니다

예

으아악

출력

으아악

시간 복잡성 – O(N*logN), str2를 반복하고 루프에서 "마지막" 인덱스의 상한을 찾기 때문입니다.

공간 복잡성 – O(N)은 맵을 사용하여 문자 인덱스를 저장하기 때문입니다.

위 내용은 문자열 B를 얻기 위해 문자열 A를 추가하는 데 필요한 최소 하위 시퀀스를 추가합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!