我希望能找到一种尽可能短的编码方式，来处理如下形式的字符串：
abbcccc = a2b4c
3个回答
0
以下是我的C++实现，用于在原地进行处理，时间复杂度为
你需要跟踪三个指针 -
O(n)，空间复杂度为O(1)。class Solution {
public:
int compress(vector<char>& chars) {
int n = (int)chars.size();
if(chars.empty()) return 0;
int left = 0, right = 0, currCharIndx = left;
while(right < n) {
if(chars[currCharIndx] != chars[right]) {
int len = right - currCharIndx;
chars[left++] = chars[currCharIndx];
if(len > 1) {
string freq = to_string(len);
for(int i = 0; i < (int)freq.length(); i++) {
chars[left++] = freq[i];
}
}
currCharIndx = right;
}
right++;
}
int len = right - currCharIndx;
chars[left++] = chars[currCharIndx];
if(len > 1) {
string freq = to_string(len);
for(int i = 0; i < freq.length(); i++) {
chars[left++] = freq[i];
}
}
return left;
}
};
你需要跟踪三个指针 -
right 用于迭代，currCharIndx 用于跟踪当前字符的第一个位置，left 用于跟踪压缩字符串的写入位置。- Kaidul
0
[注意：这个贪心算法不能保证最短解]
通过记住字符的所有先前出现，很容易找到重复字符串的第一个出现（包括所有重复的最小结束索引=在所有重复后剩余的最大字符串），并用 RLE 替换它（Python3 代码）:
def singleRLE_v1(s):
occ = dict() # for each character remember all previous indices of occurrences
for idx,c in enumerate(s):
if not c in occ: occ[c] = []
for c_occ in occ[c]:
s_c = s[c_occ:idx]
i = 1
while s[idx+(i-1)*len(s_c) : idx+i*len(s_c)] == s_c:
i += 1
if i > 1:
rle_pars = ('(',')') if len(s_c) > 1 else ('','')
rle = ('%d'%i) + rle_pars[0] + s_c + rle_pars[1]
s_RLE = s[:c_occ] + rle + s[idx+(i-1)*len(s_c):]
return s_RLE
occ[c].append(idx)
return s # no repeating substring found
为了使迭代应用的鲁棒性更强，我们必须排除一些不能应用 RLE 的情况（例如 '11' 或 '))'），同时还要确保 RLE 不会使字符串变长（当两个字符的子字符串出现两次时，例如 'abab'）。
def singleRLE(s):
"find first occurrence of a repeating substring and replace it with RLE"
occ = dict() # for each character remember all previous indices of occurrences
for idx,c in enumerate(s):
if idx>0 and s[idx-1] in '0123456789': continue # no RLE for e.g. '11' or other parts of previous inserted RLE
if c == ')': continue # no RLE for '))...)'
if not c in occ: occ[c] = []
for c_occ in occ[c]:
s_c = s[c_occ:idx]
i = 1
while s[idx+(i-1)*len(s_c) : idx+i*len(s_c)] == s_c:
i += 1
if i > 1:
print("found %d*'%s'" % (i,s_c))
rle_pars = ('(',')') if len(s_c) > 1 else ('','')
rle = ('%d'%i) + rle_pars[0] + s_c + rle_pars[1]
if len(rle) <= i*len(s_c): # in case of a tie prefer RLE
s_RLE = s[:c_occ] + rle + s[idx+(i-1)*len(s_c):]
return s_RLE
occ[c].append(idx)
return s # no repeating substring found
现在只要我们找到了一个重复的字符串，就可以安全地在先前的输出上调用
singleRLE：def iterativeRLE(s):
s_RLE = singleRLE(s)
while s != s_RLE:
print(s_RLE)
s, s_RLE = s_RLE, singleRLE(s_RLE)
return s_RLE
通过上述插入的print语句，我们可以得到以下跟踪和结果：
>>> iterativeRLE('xyabcdefdefabcdefdef')
found 2*'def'
xyabc2(def)abcdefdef
found 2*'def'
xyabc2(def)abc2(def)
found 2*'abc2(def)'
xy2(abc2(def))
'xy2(abc2(def))'
但是这个贪心算法在这个输入上失败了：
>>> iterativeRLE('abaaabaaabaa')
found 3*'a'
ab3abaaabaa
found 3*'a'
ab3ab3abaa
found 2*'b3a'
a2(b3a)baa
found 2*'a'
a2(b3a)b2a
'a2(b3a)b2a'
其中最短的解决方案之一是3(ab2a)。
- coproc
2
{btsdaf} - user5870009
{btsdaf} - coproc
0
由于贪心算法不起作用，需要进行一些搜索。这里使用了一种深度优先搜索并进行了一些修剪（如果在一个分支中字符串的前idx0个字符没有被操作，就不要试图在这些字符中查找重复的子字符串；同时，如果要替换多个子字符串出现，请对所有连续出现的子字符串进行替换）：
def isRLE(s):
"is this a well nested RLE? (only well nested RLEs can be further nested)"
nestCnt = 0
for c in s:
if c == '(':
nestCnt += 1
elif c == ')':
if nestCnt == 0:
return False
nestCnt -= 1
return nestCnt == 0
def singleRLE_gen(s,idx0=0):
"find all occurrences of a repeating substring with first repetition not ending before index idx0 and replace each with RLE"
print("looking for repeated substrings in '%s', first rep. not ending before index %d" % (s,idx0))
occ = dict() # for each character remember all previous indices of occurrences
for idx,c in enumerate(s):
if idx>0 and s[idx-1] in '0123456789': continue # sub-RLE cannot start after number
if not c in occ: occ[c] = []
for c_occ in occ[c]:
s_c = s[c_occ:idx]
if not isRLE(s_c): continue # avoid RLEs for e.g. '))...)'
if idx+len(s_c) < idx0: continue # pruning: this substring has been tried before
if c_occ-len(s_c) >= 0 and s[c_occ-len(s_c):c_occ] == s_c: continue # pruning: always take all repetitions
i = 1
while s[idx+(i-1)*len(s_c) : idx+i*len(s_c)] == s_c:
i += 1
if i > 1:
rle_pars = ('(',')') if len(s_c) > 1 else ('','')
rle = ('%d'%i) + rle_pars[0] + s_c + rle_pars[1]
if len(rle) <= i*len(s_c): # in case of a tie prefer RLE
s_RLE = s[:c_occ] + rle + s[idx+(i-1)*len(s_c):]
#print(" replacing %d*'%s' -> %s" % (i,s_c,s_RLE))
yield s_RLE,c_occ
occ[c].append(idx)
def iterativeRLE_depthFirstSearch(s):
shortestRLE = s
candidatesRLE = [(s,0)]
while len(candidatesRLE) > 0:
candidateRLE,idx0 = candidatesRLE.pop(0)
for rle,idx in singleRLE_gen(candidateRLE,idx0):
if len(rle) <= len(shortestRLE):
shortestRLE = rle
print("new optimum: '%s'" % shortestRLE)
candidatesRLE.append((rle,idx))
return shortestRLE
示例输出：
>>> iterativeRLE_depthFirstSearch('tctttttttttttcttttttttttctttttttttttct')
looking for repeated substrings in 'tctttttttttttcttttttttttctttttttttttct', first rep. not ending before index 0
new optimum: 'tc11tcttttttttttctttttttttttct'
new optimum: '2(tctttttttttt)ctttttttttttct'
new optimum: 'tctttttttttttc2(ttttttttttct)'
looking for repeated substrings in 'tc11tcttttttttttctttttttttttct', first rep. not ending before index 2
new optimum: 'tc11tc10tctttttttttttct'
new optimum: 'tc11t2(ctttttttttt)tct'
new optimum: 'tc11tc2(ttttttttttct)'
looking for repeated substrings in 'tc5(tt)tcttttttttttctttttttttttct', first rep. not ending before index 2
...
new optimum: '2(tctttttttttt)c11tct'
...
new optimum: 'tc11tc10tc11tct'
...
new optimum: 'tc11t2(c10t)tct'
looking for repeated substrings in 'tc11tc2(ttttttttttct)', first rep. not ending before index 6
new optimum: 'tc11tc2(10tct)'
...
new optimum: '2(tc10t)c11tct'
...
'2(tc10t)c11tct'
- coproc
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
a开头，然后以下一个字符的两倍重复次数继续，最后在c处停止吗？对于长度不超过2*26个字符的字符串，“唯一必要的信息”是“停止字符”，除了解压缩器/扩展器*之外：科尔莫戈洛夫复杂度。 - greybeard