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

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

王林

풀어 주다： 2023-09-10 14:41:02

앞으로

690명이 탐색했습니다.

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

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

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

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

예

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

출력– 2

지침

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

출력–3

지침

이 방법에서는 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)입니다.

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

chars를 저장하려면 "chars_mp"를 정의하고{} 키-값 쌍으로 설정하세요.
str1 문자열에 특정 문자가 존재하는 인덱스 집합을 맵에 저장합니다
"last" 및 "cnt" 변수 정의
str2 탐색을 시작합니다. 현재 문자 인덱스를 포함하는 컬렉션의 크기가 0이면 -1이 반환됩니다.
현재 문자 인덱스 세트에서 "마지막"의 상한을 찾아보세요.
상한값을 찾지 못한 경우 "cnt" 값을 1 증가시키고, "last" 값을 -1로 설정하고, "I" 값을 1 감소시킨 후 continue 키워드를 사용하세요. p>
"마지막" 변수의 값을 업데이트하세요.
루프 반복이 완료된 후 'cnt' 변수의 값을 반환합니다