주어진 문자열이 ABC의 하위 시퀀스로만 분할될 수 있는지 확인합니다.

문자열의 하위 시퀀스는 문자 순서를 변경하거나 새 문자열을 형성하지 않고 문자열의 모든 위치(0개 이상의 요소)에서 문자를 가져올 수 있는 문자열의 일부입니다. 이 문제에서는 문자열의 모든 문자가 'A', 'B' 또는 'C' 문자인 길이 N의 문자열이 제공됩니다. 우리의 임무는 문자열이 "ABC" 또는 "Not" 하위 시퀀스로만 분할될 수 있음을 찾는 것입니다. 문자열이 하위 시퀀스 "ABC"로만 분할된 경우 "yes"를 반환하고, 그렇지 않으면 "no"를 반환합니다.

으아아아

지침 - 분할 방법은 다음과 같이 문자열을 "ABC"의 하위 시퀀스 2개로 분할하는 것입니다. -

• 가능한 방법 중 하나는 인덱스 0, 2, 3의 문자를 가져와서 하위 시퀀스 "ABC"를 형성한 다음, 인덱스 1, 4, 5의 문자를 가져와서 하위 시퀀스 "ABC"를 형성하는 것입니다.

• 또 다른 가능한 방법은 인덱스 0, 4, 5와 1, 2, 3의 문자를 가져와 하위 시퀀스 "ABC"를 형성하는 것입니다.

따라서 문자열은 "ABC"의 2개 하위 시퀀스로 분할될 수 있습니다.

으아아아

설명 - 인덱스 5번에 나오는 'A'의 경우 그 뒤에 'B'가 없습니다. 따라서 전체 문자열을 고유한 하위 시퀀스 "ABC"로 분할할 수 없습니다. 그러므로 대답은 "아니요"입니다.

방법 1: 해시맵 사용

다음과 같이 두 가지 관찰 결과가 있습니다. -

• 문자열을 "ABC"로 분할해야 하고 문자 'A', 'B', 'C'의 개수가 같아야 하므로 문자열의 크기는 3으로 나누어야 합니다. 그렇지 않으면 조건을 충족할 수 없습니다.

• 문자 "A", "B" 및 "C"의 빈도를 계산할 때 'A'의 개수는 'B'의 개수보다 크거나 같아야 하며 'B'의 개수는 더 커야 합니다. 'C'의 개수와 같거나 같습니다. 왜냐하면 A의 개수 >= B의 개수 >= C의 cout

위의 관찰을 바탕으로 확인해야 할 세 가지 조건이 있습니다.

• 문자열 크기 % 3 == 0이어야 합니다.

• A의 개수 >= B의 개수 >= C의 개수여야 합니다.

• 마지막 조건은 freq[ 'A' ] == freq[ 'B' ] == freq[ 'C' ] 여야 합니다.

주어진 문자열 "str"에 각 문자의 빈도를 저장해야 하므로 해시 맵을 사용하여 이 문제를 해결할 수 있습니다.

아래 방법을 단계별로 논의해 보겠습니다.

• 먼저, 주어진 문자열 "str"을 매개변수로 취하고 가능하면 원하는 문자열 "yes"를 반환하는 "checkSubsequences"라는 함수를 생성하고, 그렇지 않으면 "no"를 반환 값으로 반환합니다.

• 함수에서 모든 단계는 다음과 같습니다. -

• 문자열의 길이를 저장하는 변수 "len"을 만듭니다.

• 첫 번째 조건을 확인하고 길이가 3으로 나누어지지 않으면 'no'를 반환합니다.

• 'A', 'B', 'C' 문자의 빈도를 저장하는 해시 맵을 만듭니다. 따라서 공간복잡도는 일정하다.

• for 루프를 사용하여 문자열을 0에서 len 미만까지 순회합니다.

  • 문자열의 현재 문자 수 늘리기

  • 두 번째 조건을 확인하고 "A"의 개수가 "B"의 개수보다 작거나 "B"의 개수가 "C"의 개수보다 작은 경우 "No"를 반환합니다.

    li>

• for 루프 후에 마지막 세 번째 조건을 확인하고 A의 개수가 B의 개수와 같지 않거나 B의 개수가 C의 개수와 같지 않으면 "No"를 반환해야 합니다.

• 마지막으로 모든 조건이 충족되면 "yes"를 반환합니다.

예

으아아아

출력

으아아아

시간과 공간의 복잡성

위 코드의 시간 복잡도는 문자열을 반복하기 때문에 O(N)입니다. 여기서 N은 문자열의 크기입니다.

위 코드의 공간 복잡도는 크기가 3인 숫자의 빈도를 저장하기 때문에 O(1)입니다.

결론

이 튜토리얼에서는 주어진 문자열을 하위 시퀀스 ABC로만 분할할 수 있는지 확인하는 프로그램을 구현했습니다. 빈도를 저장해야 했기 때문에 해싱 방법을 구현했습니다. 이 방법에서는 주로 세 가지 조건을 확인합니다. 모든 조건이 충족되면 문자열을 "ABC"의 하위 시퀀스로만 분할할 수 있음을 의미합니다.

위 내용은 주어진 문자열이 ABC의 하위 시퀀스로만 분할될 수 있는지 확인합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!