时间戳

首页 > 解决方案 > Python找到具有运行长度编码的最小长度压缩字符串，我们可以删除n个连续字符以获得最小长度

python - Python找到具有运行长度编码的最小长度压缩字符串，我们可以删除n个连续字符以获得最小长度

问题描述

我们有字符串'AABCAA'，如果我们对这个字符串进行运行长度编码，我们会得到'2ABC2A'。长度为 6。我们可以选择从字符串中删除 N 个连续字符。我们应该找到最小长度的运行长度压缩字符串

需要找到通过删除两个连续字符形成的所有子字符串 

'BCAA' --->BC2A --->4  
'ACAA' --->AC2A --->4  
'AAAA' --->4A --->2  
'AABA' --->2ABA ---> 4  
'AABC' --->2ABC ---> 4

在这个答案中是'4A'

下面是代码，有没有办法以更少的时间和空间复杂度来实现这一点？？？？？？

'''

    **def run_len_encoding_removing_n(s,n):
        m=len(encoding(s))
        s1=encoding(s)
        for i in range(len(s)-n+1):
                #l.append(s[:i] + s[i+n :])
                print(s[:i] + s[i+n :])
                r=encoding(s[:i] + s[i+n :])
                if len(r)< m:
                    m=len(r)
                    s1=r
        print(m)
        print(s1)

    def encoding(s):
        encoded_message=""
        i=0
        while i < len(s):
            cnt=1
            j=i
            while j < len(s)-1:
                if s[j]==s[j+1]:
                    cnt=cnt+1
                    j=j+1
                else:
                    break
            encoded_message=encoded_message + str(cnt)+s[i]
            i=j+1
        return encoded_message



    if __name__ == '__main__':
        n = 2
        s = 'AABCAA'
        run_len_encoding_removing_n(s,n)**

'''

标签： pythonalgorithm

解决方案

# space complexity O(1)
# time complexity O(n)

# greedy: we will remove the first two characters which will increase matches

def encode(s):
  to_remove = []
  for i in range(len(s)-2):

    # if match continue
    if i in to_remove:
      continue
    if s[i] == s[i+1]:
      continue
    elif s[i] == s[i+2] and len(to_remove) <= 1:
      # let's remove i+1 to increase match
      to_remove.append(i+1)
    elif s[i] == s[i+3] and len(to_remove) == 0:
      to_remove.append(i+1)
      to_remove.append(i+2)

    if len(to_remove) == 2:
      return to_remove

    else:
      if len(to_remove) == 0:
        return [0,1]
      elif len(to_remove) == 1:
        return to_remove + [len(s)-to_remove[0]]  # any choice will work

encode('AAAACAA')

推荐阅读