문자열 압축. 페이스북 면접 질문입니다.

질문: 문자열을 압축한 다음 디코딩하는 시스템을 설계하십시오. 입력은 알파벳 문자로만 구성됩니다.

예: 문자열이 다음과 같은 경우: 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

버그와 엣지 케이스를 지적해 주신 커뮤니티에 특별히 감사드립니다!! 🥰