문자열 압축 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 * 10⁵
• 단어는 영문 소문자로만 구성됩니다.

힌트:

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!