字符串压缩。Facebook面试题。
问题：设计一个系统，对字符串进行压缩和解码。输入字符串仅包含字母字符。
例如：如果字符串是：aaabbcccccd
1> 它的压缩形式，即编码形式将是 a3b3c5d1。
2> 那么我们需要获取压缩字符串并对其进行解码。
注意：这是一个字符串操作问题，旨在测试你的字符串操作技能，不要将其与压缩算法混淆，因为还有更好的压缩算法。
想象一下类似这样的系统： 字符串“Richard is great but you know”被压缩成 RIGBY，客户端和服务器都知道这个字符串代表什么。
人们可以将其用于自己的项目中：
字符串编码/压缩
算法很简单，就是保存指针并继续执行。统计字符重复出现的次数，并将该字符及其重复次数添加到结果字符串中。
var encode = function(string){
let chars = string.split("");
let res = "";
for(let i=0;i<chars.length;i++){
let count = 1; //default count = 1 since at least 1 character
let char = chars[i]; //the character at that pointer
while(i<chars.length-1 && chars[i] == chars[i+1]){
count++; // increment the count
i++; // increment the pointer
}
res += char + count; // append to resultant string.
}
return res;
}
解码字符串
解码字符串的过程也类似，我们保留一个指针，获取字符，获取其计数，生成一个字符并将其附加到结果字符串中。
var decode = function(string){
let res = "";
for(let i=0;i<string.length;){
let char = string[i];
let count = 0;
i++;
while(i<string.length && parseInt(string[i])>=0 && parseInt(string[i])<=9){
count = parseInt(count * 10) + parseInt(string[i]);
i++;
}
while(count>0){
res+= char;
count--;
}
}
return res;
}
将它们结合起来：
var encode = function(string){
let chars = string.split("");
let res = "";
for(let i=0;i<chars.length;i++){
let count = 1;
let char = chars[i];
while(i<chars.length-1 && chars[i] == chars[i+1]){
count++;
i++;
}
res += char + count;
}
return res;
}
var decode = function(string){
let res = "";
for(let i=0;i<string.length;){
let char = string[i];
let count = 0;
i++;
while(i<string.length && parseInt(string[i])>=1 && parseInt(string[i])<=9){
count = parseInt(count * 10) + parseInt(string[i]);
i++;
}
while(count>0){
res+= char;
count--;
}
}
return res;
}
let compress = encode("aaabbbccccccccccccd");
console.log(compress);
let res = decode(compress);
console.log(res);
好了，现在你知道如何解答 Facebook 面试题了，并且对压缩技术也有了一些了解。
github：https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/stringCompression.js
特别感谢社区成员指出bug和特殊情况！！🥰
文章来源：https://dev.to/akhilpokle/string-compression-facebook-interview-question-3d2o