สมมติว่าเรามีรายการคำ เราอาจเข้ารหัสโดยการเขียนสตริงอ้างอิง S และรายการดัชนี A ตัวอย่างเช่น ให้เราพิจารณาว่ารายการคำคือ ["เวลา" "ฉัน" "กระดิ่ง" หรือไม่ ] จากนั้นเราสามารถเขียนเป็น S ="time#bell#" และ indexes =[0, 2, 5] ที่นี่สำหรับแต่ละดัชนี เราจะกู้คืนคำโดยการอ่านจากสตริงอ้างอิงจากดัชนีนั้นจนกว่าจะถึงสัญลักษณ์ "#"
ดังนั้นเราต้องหาความยาวของสตริงอ้างอิงที่สั้นที่สุด S ที่เป็นไปได้ที่เข้ารหัสคำที่กำหนด? สำหรับตัวอย่างที่กำหนด ผลลัพธ์จะเป็น 10
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดเมธอด insertNode ซึ่งจะใช้ส่วนหัวและสตริง s
- curr :=head, flag :=false.
- สำหรับ i ในช่วงขนาด s – 1 เหลือ 0
- x :=s[i]
- ถ้า m[x] ของ curr เป็นโมฆะ ให้ตั้งค่า flat :=true และสร้างโหนดใหม่เป็น m[x] ของ curr
- curr :=m[x] ของสกุลเงิน
- ขนาดส่งคืนของ s เมื่อแฟล็กเป็นจริง มิฉะนั้น 0
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- ret :=0, head :=โหนดใหม่
- จัดเรียงอาร์เรย์คำตามความยาว
- n :=ขนาดของคำ
- สำหรับ i ในช่วง 0 ถึง n – 1
- temp :=insertNode(head, words[i])
- ถ้า temp ไม่ใช่ 0 แล้ว ret :=ret + temp + 1
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
struct Node{
map <char, Node*> m;
};
class Solution {
public:
static bool cmp(string a, string b){
return a.size() > b.size();
}
int insertNode(Node* head, string s){
Node* curr = head;
bool flag = false;
for(int i = s.size() - 1; i >= 0; i--){
char x = s[i];
if(!curr->m[x]){
flag = true;
curr->m[x] = new Node();
}
curr = curr->m[x];
}
return flag? (int)s.size() : 0;
}
int minimumLengthEncoding(vector<string>& words) {
int ret = 0;
Node* head = new Node();
sort(words.begin(), words.end(), cmp);
int n = words.size();
for(int i = 0; i < n; i++){
int temp= insertNode(head, words[i]);
if(temp){
ret += (temp + 1);
}
}
return ret;
}
};
main(){
vector<string> v = {"time", "me", "bell"};
Solution ob;
cout << (ob.minimumLengthEncoding(v));
} อินพุต
["time", "me", "bell"]
ผลลัพธ์
10
