문자열 압축

문제 설명 : 주어진 문자열을 압축하는 함수를 작성하십시오. 공간을 절약하는 경우에만 압축된 문자열을 반환합니다.



난이도: 쉬움




테스트 케이스


  • 'AAABAACCDDDD' ---> 'A3BA2C2D4'
  • 'BAAACCDDDD' ---> 'BA3C2D4'
  • 'AABBCC' --> 'AABBCC'
  • 'BBBAACCCCDD' --> 'B3A2C4D2'



  • 연산


  • 문자열의 첫 번째 문자에 포인터를 설정하고 빈 문자열과 카운터를 초기화합니다.
  • 문자열을 반복하고 문자가 문자열의 첫 번째 문자와 같은지 확인합니다.
  • 둘 다 동일한 증분 카운터인 경우.



  • 또 다른,
  • 첫 번째 문자를 추가하고 결과 문자열에 카운트합니다.
  • count가 1보다 크면 결과 문자열에만 count를 추가합니다.
  • 그렇지 않으면 결과 문자열에 빈 문자열을 추가합니다.

  • 이제 첫 번째 문자가 현재 문자가 됩니다.
  • 카운터 값을 1로 재설정하십시오.

  • 마지막 문자를 추가하면 결과 문자열에 카운트됩니다.
  • 길이가 주어진 문자열보다 작으면 압축된 결과 문자열을 반환하고, 그렇지 않으면 주어진 문자열을 반환합니다.

  • 시간 및 공간 복잡성


  • 시간 복잡도: O(n)
  • 공간 복잡도: O(n)



  • 암호



    class CompressString(object):
        def compress(self, input):
            if input is None or not input:
                return input
            result = ''
            count = 0
            prev_char = input[0]
            for char in input:
                if char == prev_char:
                    count += 1
                else:
                    result += prev_char + (str(count) if count > 1 else '')
                    prev_char = char
                    count = 1
            result += prev_char + (str(count) if count > 1 else '')
            return result if len(result) < len(input) else input
    

    More precise compression



    class CompressString(object):
        def compress(self, input):
            if input is None or not input:
                return input
            result = ''
            count = 0
            prev_char = input[0]
            for char in input:
                if char == prev_char:
                    count += 1
                else:
                   if count > 2:
                        result += prev_char + (str(count))
                        prev_char = char
                        count = 1
                   elif count == 1:
                        result += prev_char
                        count = 1
                        prev_char = char
                   else:
                        result += prev_char
                        result += prev_char
                        count = 1
                        prev_char = char
            result += prev_char + (str(count) if count > 2 else prev_char)
            return result if len(result) < len(input) else input
    

    테스트



    import unittest
    from compressString import CompressString
    
    
    class TestCompress(unittest.TestCase):
    
        def testCompress(self, func):
            self.assertEqual(func(None), None)
            self.assertEqual(func(''), '')
            self.assertEqual(func('AABBCC'), 'AABBCC')
            self.assertEqual(func('AAABCCDDDDE'), 'A3BC2D4E')
            self.assertEqual(func('BAAACCDDDD'), 'BA3C2D4')
            self.assertEqual(func('AAABAACCDDDD'), 'A3BA2C2D4')
            print('Success: testCompress')
    
    
    def main():
        test = TestCompress()
        compress_string = CompressString()
        test.testCompress(compress_string.compress)
    
    
    if __name__ == '__main__':
        main()
    

    Original article

    Github solution

    행복한 코딩!

    좋은 웹페이지 즐겨찾기