Leetcode (443) Сжатие строк

Это вопрос, который я пробовал Leetcode: сжатие строк

Учитывая массив символов chars, сожмите его, используя следующий алгоритм:

Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в символах:

Если длина группы равна 1, добавьте символ к s. В противном случае добавьте символ, за которым следует длина группы. Сжатую строку s не следует возвращать отдельно, а вместо этого следует хранить во входном массиве символов chars. Обратите внимание, что группы длиной 10 или более будут разделены на несколько символов в символах.

После того, как вы закончите изменять входной массив, верните новую длину массива.

Вы должны написать алгоритм, который использует только постоянное дополнительное пространство.

Я пытался решить это решение в На) временная сложность. Хотя я и сделал это, это намного медленнее.

    def compress(self, chars: List[str]) -> int:
        i = 0
        while i < len(chars):
            count = 0
            for char in chars[i:]:
                if char != chars[i]:
                    break
                count += 1
            if count != 1:
              list_appending = list(str(count))
              chars[i+1:i+count] = list_appending
              i += 1 + len(list_appending)  
            else:
              i += 1
            
        return len(chars)

Пожалуйста, объясните причину, по которой мое решение не такое быстрое ?? Почему мое решение O (n) для сжатия строк Leetcode (443) не оптимально?

Это не $ O (п) $ но $ O (п ^ 2) $, потому что:

• chars[i:] берет $ O (п) $ время и место. Вместо этого вы можете переместить второй индекс j вперед до последнего вхождения, а затем вычислить длину как j - i + 1.
• chars[i+1:i+count] = list_appending берет $ O (п) $ время. Вместо замены всех count одинаковые символы, лучше заменить ровно столько цифр, сколько вам нужно. Тогда оставшиеся символы не перемещаются, и это $ O (1) $ (амортизировано).

Вы сокращаете список. Я бы сказал, что вы не должны этого делать. Если вы должны были сократить список, зачем им возвращать длину списка? Я думаю, вы должны записать сжатые данные в префикс списка и вернуться туда, где эти сжатые данные заканчиваются. Как они просили в более ранняя проблема.

Преобразование str(count) в список не нужно. И я бы нашел digits более значимое имя, чем list_appending.

PEP 8 предлагает написать chars[i+1:i+count] в качестве chars[i+1 : i+count] (и я согласен).

По сути, это работа для itertools.groupby, вот решение, использующее это:

    def compress(self, chars: List[str]) -> int:
        def compress():
            for c, g in groupby(chars):
                yield c
                k = countOf(g, c)
                if k > 1:
                    yield from str(k)
        for i, chars[i] in enumerate(compress()):
            pass
        return i + 1

Просто для удовольствия плохое, но также быстрое решение для регулярных выражений:

    def compress(self, chars: List[str]) -> int:
        chars[:] = re.sub(
            r'(.)1+',
            lambda m: m[1] + str(len(m[0])),
            ''.join(chars))
        return len(chars)