문자열 압축 III

Susan Sarandon
풀어 주다: 2024-11-05 07:08:02
원래의
418명이 탐색했습니다.

String Compression III

3163. 문자열 압축 III

난이도:

주제: 문자열

문자열 단어가 주어지면 다음 알고리즘을 사용하여 압축합니다.

  • 빈 문자열 구성 요소로 시작하세요. 단어가 비어 있지 아닌 동안 다음 작업을 사용하세요.
    • 단일 문자로 구성된 단어의 최대 길이 접두사를 제거합니다. c 최대 9회
    • 반복됩니다.
    • comp에 접두사의 길이와 c를 추가합니다.

문자열 comp를 반환합니다.

예 1:

  • 입력: 단어 = "abcde"
  • 출력: "1a1b1c1d1e"
  • 설명: 처음에는 comp = ""입니다. 각 작업의 접두사로 "a", "b", "c", "d" 및 "e"를 선택하여 작업을 5번 적용합니다.
    • 각 접두사에 대해 "1" 뒤에 문자를 추가하여 구성합니다.

예 2:

  • 입력: 단어 = "aaaaaaaaaaaaabb"
  • 출력: "9a5a2b"
  • 설명: 처음에는 comp = ""입니다. 각 작업의 접두사로 "aaaaaaaaa", "aaaaa" 및 "bb"를 선택하여 작업을 3번 적용합니다.
    • 접두사 "aaaaaaaaa"의 경우 "9" 뒤에 "a"를 추가하여 구성합니다.
    • 접두사 "aaaaa"의 경우 "5" 뒤에 "a"를 추가하여 구성합니다.
    • 접두사 "bb"의 경우 "2"를 추가하고 "b"를 붙여서 구성합니다.

제약조건:

  • 1 <= 단어.길이 <= 2 * 105
  • 단어는 영문 소문자로만 구성됩니다.

힌트:

  1. 매번 접두사에서 동일한 문자를 최대 9번까지 잘라냅니다. 항상 더 큰 접두사를 자르는 것이 좋습니다.

해결책:

탐욕적인 접근 방식을 사용하여 반복 문자의 가능한 가장 긴 접두사(한 번에 최대 9개 발생)를 가져온 다음 해당 문자와 ​​함께 접두사의 길이를 결과에 추가하여 문자열을 압축할 수 있습니다.

단계별 해결 방법은 다음과 같습니다.

  1. 변수 초기화:

    • comp(압축된 문자열)는 빈 문자열로 시작합니다.
    • 포인터나 인덱스 i를 사용하여 단어의 위치를 ​​추적하세요.
  2. 단어 반복:

    • 단어에 남은 문자가 있는 동안, 9자를 넘지 않는 반복문자 중 가장 긴 접두어를 찾아보세요.
    • 현재 문자가 연속해서 반복되는 횟수를 최대 9회까지 계산합니다.
  3. 압축된 문자열에 추가:

    • 카운트 뒤에 문자를 추가하여 구성하세요.
    • 포인터 i를 처리된 문자 수만큼 앞으로 이동합니다.
  4. 반품 결과:

    • 전체 문자열을 처리한 후 압축된 문자열 comp를 반환합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 3163. 문자열 압축 III






설명:

  • 계산 루프: 메인 루프 내에서 while 루프를 사용하여 단어의 각 고유 문자에 대해 연속 문자(최대 9개)를 계산합니다.
  • 결과 추가: 각 시퀀스를 계산한 후 개수와 문자를 comp에 직접 추가합니다.
  • 포인터 업데이트: 기본 루프 포인터 i가 계산된 문자 수만큼 앞으로 이동하여 각 반복에서 나머지 문자열의 크기를 효과적으로 줄입니다.

복잡성 분석

  • 시간 복잡도: O(n), 여기서 n은 단어의 길이입니다. 각 문자는 한 번씩 처리됩니다.
  • 공간 복잡도: comp에 저장된 압축 결과의 경우 O(n)

이 솔루션은 효율적이며 9자보다 짧은 시퀀스나 각 문자의 단일 발생과 같은 극단적인 경우를 처리합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

  • 링크드인
  • 깃허브

위 내용은 문자열 압축 III의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:dev.to
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿