简单的字符串压缩：删除连续的重复子字符串
最近我在亚马逊的一次采访中被问到了这个问题。
给定一个字符串，从中删除连续的重复子字符串。 如果有多个连续的相交子字符串，请删除其中最大的那个。
为了说清楚，下面是一些例子：
aabcccddeaaa 输出：
abcdea （压缩连续的重复字符） abababcdeee 输出：
abcde （压缩连续重复的子串） ababcdabcd 输出：
ababcd （你可以压缩' ab '或' abcd '，但由于' abcd '的长度较大，所以你最好压缩较大的一个。）
我不能提出一个有效的实现，任何人都知道一个好办法呢？
由于这是面试问题，请避免使用复杂的图书馆功能。
没有正则表达式...这种递归方法的工作原理：
var cases = ['aabcccddeaaa', 'abababcdeee', 'ababcdabcd'];
function compress(str) {
var len, sub, i, n;
// if str is shorter than 2, can't be any repeating substrings
if(str.length < 2)
return str;
// max meaningful length is str.length/2 (truncated to integer)
for(len = (str.length / 2) | 0; len > 0; len--) {
// search for a repeating substring of "len" length starting at index i
for(i = 0; i + (len * 2) <= str.length; i++) {
sub = str.substr(i, len);
// if such a substring exists...
if(str.indexOf(sub, i + len) == i + len) {
// "count" how many occurences (advance index till beyond repeats)
for(n = i + len * 2; str.indexOf(sub, n) == n; n += len);
// return a string composed of the compressed part before the match +
// the substring + the compressed part beyond the match
return compress(str.substr(0, i)) + sub + compress(str.substr(n));
}
}
}
// if nothing found, return original string
return str;
}
alert(JSON.stringify(cases.map(compress))); 对于字符串X ，我们可以使用Z算法找到O（n ^ 2）中最大的连续重复子字符串， Given a string S of length n, the Z Algorithm produces an array Z where Z[i] is the length of the longest substring starting from pat[i] which is also a prefix of pat （Source） Given a string S of length n, the Z Algorithm produces an array Z where Z[i] is the length of the longest substring starting from pat[i] which is also a prefix of pat
对于X每个后缀，从i开始，对此子字符串应用Z算法：
int result = 0;
for(int i = 0; i < X.length(); i++)
int[]z = Z-algo(X.substring(i)); //this take O(n)
for(int j = i + result + 1; j < X.length(); j++)
if(z[j] >= j - i + 1)
result = (j - i + 1);
重复上述过程直到找不到任何重复的子串，我们可以获得一个O（n ^ 3）算法。
注意 ：重读这个问题后，特别是最后一个例子，我发现有效的重复子串只受原始子串的限制。 因此，通过使用最大堆，可以将时间复杂度降低到O（n ^ 2 log n）。
pos=[]
dstr={}
final=[]
x="ababcdabcdcde"
for k in re.finditer(r"(?=(.+?)1+)",x): #Find start of all overlapping strings
pos.append(k.start())
i=0
for k in pos: #Find end of overlapping strings
s=re.findall(r"^((.*)2+)",x[k:])
dstr[i]=(k,len(s[0][0]))
i=i+1
#print dstr.values()
k=0
while k< len(dstr.values())-1: #remove smaller length overlapping result
if dstr.values()[k+1][0]<dstr.values()[k][1]<dstr.values()[k+1][1]:
pass
else:
final.append(dstr.values()[k][0])
k=k+1
if dstr.values()[k-1][0] in final:
pass
else:
final.append(dstr.values()[k][0])
#print final
for k in final: #remove strings
s=re.sub(r"(.*)1+",r"1",x[k:])
x=x[:k]+s
print x
这是在python.Works与给定的输入罚款。
链接地址: http://www.djcxy.com/p/86563.html上一篇: Simple string compression: removing consecutive repeating substrings