문자열을 세 개의 하위 문자열로 분할할 수 있는지 확인합니다. 여기서 하나의 하위 문자열은 다른 두 하위 문자열의 하위 문자열입니다.

이 문제에서는 세 번째 하위 문자열이 처음 두 하위 문자열의 하위 문자열이 될 수 있도록 주어진 문자열을 분할해야 합니다.

해결책을 생각해 봅시다. 세 번째 문자열은 처음 두 문자열이 세 번째 문자열의 모든 문자를 포함하는 경우에만 처음 두 문자열의 하위 문자열이 될 수 있습니다. 따라서 주어진 문자열에서 빈도가 3보다 큰 문자를 하나 이상 찾아야 하며 해당 단일 문자의 세 번째 하위 문자열을 가져올 수 있습니다.

문제 설명 - N개의 소문자 알파벳 문자를 포함하는 문자열 str이 제공됩니다. 문자열을 세 개의 부분 문자열 a, b, c로 분할하여 부분 문자열 c가 a와 b의 부분 문자열이 되도록 할 수 있는지 확인해야 합니다. 3개의 하위 문자열을 찾을 수 있는지 여부에 따라 "yes" 또는 "no"를 인쇄합니다.

예

으아아아 으아아아

지침

여기서 문자열을 "tu", "torialsPoin" 및 "t"로 나눌 수 있습니다. 따라서 세 번째 문자열은 처음 두 문자열의 하위 문자열입니다.

으아아아 으아아아

지침

문자의 빈도가 3보다 크지 않기 때문에 주어진 조건에 따라 문자열을 세 개의 하위 문자열로 분할할 수 없습니다.

으아아아 으아아아

지침

주어진 조건에 따라 세 개의 하위 문자열 은 'h', 'h' 및 'hhhhhh'가 될 수 있습니다.

방법 1

이 방법에서는 배열을 사용하여 각 문자의 빈도를 저장합니다. 그런 다음 빈도가 3보다 크거나 같은 문자를 확인합니다.

알고리즘

• 1단계 - 길이가 26인 "freq" 배열을 정의합니다.

• 2단계 - 문자열을 반복하여 문자의 빈도를 계산합니다. for 루프에서 freq[str[i] – 'a'] 값을 늘립니다. 여기서 str[i] – 'a'는 0에서 26 사이의 인덱스를 제공합니다.

• 3단계 - 이제 "freq" 배열을 반복하고 배열 인덱스의 값이 "3"보다 크면 true를 반환합니다.

• 4단계 - 루프가 종료되면 true를 반환합니다.

• 5단계 - isSUbStringPossible() 함수의 반환 값에 따라 "Yes" 또는 "No"를 인쇄합니다.

예

으아아아

출력

으아아아

시간 복잡도 - O(N), 문자열을 반복할 때.

공간 복잡도 - 일정한 길이의 배열을 사용하므로 O(1)입니다.

방법 2

이 방법에서는 먼저 문자열을 문자 배열로 변환합니다. 그런 다음 count() 메서드를 사용하여 배열에서 특정 문자의 빈도를 계산합니다.

알고리즘

• 1단계 - "len + 1" 크기의 배열을 만듭니다. 여기서 "len"은 문자열 길이입니다.

• 2단계 - strcpy() 메서드를 사용하여 문자열을 char 배열로 복사합니다.

• 3단계 - for 루프를 사용하여 총 26번 반복합니다.

• 4단계 - for 루프에서 count() 메서드를 사용하여 특정 문자의 발생 횟수를 계산합니다.

count() 메서드는 시작 위치에 대한 참조를 첫 번째 인수로, 끝 위치에 대한 참조를 두 번째 인수로, 문자를 세 번째 인수로 사용합니다.

여기서 문자의 ASCII 값을 매개변수로 전달해야 하며 I + 'a'를 사용하여 값을 가져옵니다.

• 5단계 - count() 메서드가 3보다 크거나 같으면 true를 반환합니다.

• 6단계 - 루프가 종료되면 false를 반환합니다.

예

으아아아

출력

으아아아

시간 복잡도 - O(N) count() 메서드가 문자 배열을 반복하여 문자 수를 계산하기 때문입니다. 또한 strcpy() 메서드는 O(N) 시간이 걸립니다.

공간 복잡도 - 문자열을 문자 배열에 저장하기 때문에 O(N)입니다.

결론

하나의 하위 문자열이 두 개의 다른 하위 문자열의 하위 문자열이 될 수 있도록 문자열을 세 개의 하위 문자열로 분할하는 두 가지 방법을 배웠습니다. 두 번째 방법의 코드는 더 읽기 쉽고 초보자에게 친숙하지만 시간과 공간이 더 많이 소요됩니다.

위 내용은 문자열을 세 개의 하위 문자열로 분할할 수 있는지 확인합니다. 여기서 하나의 하위 문자열은 다른 두 하위 문자열의 하위 문자열입니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!