สมมติว่ามีรายการสตริง เราต้องออกแบบอัลกอริทึมที่เข้ารหัสรายการสตริงเป็นสตริงเดียว และทำ decoder ที่ถอดรหัสกลับเป็นรายการสตริงต้นฉบับ สมมติว่า encoder และ decoder ติดตั้งบนเครื่องเหล่านี้ และมีฟังก์ชันสองตัวดังนี้ −
Machine 1 (sender) มีฟังก์ชัน
string encode(vector<string> strs) { //โค้ดอ่านสตริงและคืนค่า encoded_string; } Machine 2 (receiver) มีฟังก์ชัน
vector<string> decode(string s) { //โค้ดถอดรหัส encoded_string และคืนค่า strs; } เช่น ถ้าอินพุทเป็น {"hello", "world", "coding", "challenge"} ผลลัพธ์จะเป็น Encoded String 5#hello5#world6#coding9#challenge decoded form [hello, world, coding, challenge, ]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
กำหนดฟังก์ชัน encode() รับอาร์เรย์ strs
ret := สตริงว่าง
ลูป i := 0 ถึงขนาดของ strs-1 ทำ −
ret := ret ต่อ ขนาดของ strs[i]
คืนค่า ret
กำหนดฟังก์ชัน getNext() รับ x, start, s
idx := ขนาดของ s
ลูป i := start ถึงขนาดของ s-1 ทำ −
ถ้า s[i] เท่ากับ x แล้ว −
idx := i
ออกจากลูป
คืนค่า idx
กำหนดเมธอด decode รับ s
กำหนดอาร์เรย์ ret
i := 0
n := ขนาดของ s
ลูป while i < n ทำ −
hashPos := getNext('#', i, s)
len := (substring ของ s จากดัชนี (i ถึง hashPos - i - 1) เป็นจำนวนเต็ม
i := hashPos + 1
แทรก substring ของ s จากดัชนี (i ถึง len - 1) ที่ท้ายของ ret
i := i + len
คืนค่า ret
ตัวอย่าง
ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −
#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, ]
