Рубрики
Без рубрики

Сжатие строки

Оператор задачи: Напишите функцию для сжатия данной строки. Только верните сжатый … Помечено Python, Strings, Office Obsters.

Массивы/струны проблемы кодирования (4 серии деталей)

Оператор задачи: Напишите функцию для сжатия данной строки. Верните сжатую строку, только если она сохраняет пространство.

Сложный уровень: Легкий

Тестовые случаи

  • ‘Aaabaaccdddd’ —> ‘a3ba2c2d4’
  • ‘Baaaccdddd’ —> ‘ba3c2d4’
  • ‘Aabbcc’ -> ‘aabbcc’
  • ‘Bbbaaccccdd’ -> ‘b3a2c4d2’

Алгоритм

  • Установите указатель на первый символ строки, инициализируйте пустую строку и счетчик.
  • Итерация через строку и проверьте, равен ли символ первого символа строки.
    • Если оба стоят счетчик приращения.

  • Еще,

    • Добавьте первый символ, и его счет для получения строки.
      • Если счет больше 1, то добавьте только счет к строке результата.
      • Иначе добавьте пустую строку в строку результата.
    • Теперь первым персонажем будет текущий персонаж.
    • сбросить значение счетчика до 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

Более точное сжатие

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()

Оригинальная статья

GitHub Solution

Счастливого кодирования!

Массивы/струны проблемы кодирования (4 серии деталей)

Оригинал: “https://dev.to/codewithml/string-compression-3hgb”

Читайте ещё по теме: