문자열 목록이 있다고 가정합니다. 문자열 목록을 문자열로 인코딩할 수 있는 알고리즘을 설계해야 합니다. 또한 문자열의 원래 목록으로 다시 디코딩할 디코더를 하나 만들어야 합니다. 이 기계에 인코더와 디코더가 설치되어 있고 다음과 같은 두 가지 기능이 있다고 가정합니다. -
머신 1(발신자)에는 기능이 있습니다.
string encode(vector<string< strs) { //code to read strings and return encoded_string; }
머신 2(수신기)에는 기능이 있습니다.
vector<string< decode(string s) { //code to decode encoded_string and returns strs; }
따라서 입력이 {"hello", "world", "coding", "challenge"}와 같으면 출력은 Encoded String 5#hello5#world6#coding9#challenge, 디코딩된 형식 [hello, world, coding , 도전, ]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
함수 encode()를 정의하면 배열 strs가 필요합니다.
-
ret :=빈 문자열
-
for initialize i :=0, i
-
ret :=ret strs[i]
의 크기 연결
-
-
리턴 렛
-
getNext() 함수를 정의하면 x, start, s,
가 필요합니다. -
idx :=s의 크기
-
for initialize i :=start, i
-
s[i]가 x와 같으면 -
-
idx :=나는
-
루프에서 나오세요
-
-
-
IDx를 반환
-
이 작업에 소요되는 메서드 디코딩 정의
-
ret 배열 정의
-
나는 :=0
-
n :=s
의 크기 -
나는
-
hashPos :=getNext('#', i, s)
-
len :=(인덱스(i에서 hashPos - i - 1까지) s의 부분 문자열을 정수로
-
나는 :=hashPos + 1
-
ret의 끝에 인덱스(i부터 len - 1까지)의 s 부분 문자열 삽입
-
나는 :=나는 + len
-
-
리턴 렛
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto< v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Codec { public: string encode(vector<string>& strs) { string ret = ""; for (int i = 0; i < strs.size(); i++) { ret += to_string(strs[i].size()) + "#" + strs[i]; } return ret; } int getNext(char x, int start, string s){ int idx = s.size(); for (int i = start; i < s.size(); i++) { if (s[i] == x) { idx = i; break; } } return idx; } vector<string> decode(string s) { vector<string> ret; int i = 0; int n = s.size(); while (i < n) { int hashPos = getNext('#', i, s); int len = stoi(s.substr(i, hashPos - i)); i = hashPos + 1; ret.push_back(s.substr(i, len)); i += len; } return ret; } }; main(){ Codec ob; vector<string> v = {"hello", "world", "coding", "challenge"}; string enc = (ob.encode(v)); cout << "Encoded String " << enc << endl; print_vector(ob.decode(enc)); }
입력
{"hello", "world", "coding", "challenge"}
출력
Encoded String 5#hello5#world6#coding9#challenge [hello, world, coding, challenge, ]