資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中單詞的短編碼
假設我們有一列單詞，我們可以透過編寫一個參考字串S和一個索引列表A來對其進行編碼。例如，如果單詞列表是["time", "me", "bell"]，那麼我們可以將其寫成S = "time#bell#"和索引 = [0, 2, 5]。對於每個索引，我們將從該索引處的參考字串讀取，直到到達"#"符號，從而恢復單詞。
因此，我們必須找到能夠對給定單詞進行編碼的最短參考字串S的長度是多少？對於給定的示例，輸出將為10。
為了解決這個問題，我們將遵循以下步驟：
- 定義insertNode方法，該方法將接收頭部和字串s
- curr := head，flag := false。
- 對於s大小減1到0範圍內的i
- x := s[i]
- 如果curr的m[x]為空，則設定flat := true並建立一個新節點到curr的m[x]中。
- curr := curr的m[x]
- 當flag為true時返回s的大小，否則返回0
- 從主方法中，執行以下操作：
- ret := 0，head := 新節點
- 根據單詞的長度對words陣列進行排序
- n := words的大小
- 對於0到n-1範圍內的i
- temp := insertNode(head, words[i])
- 如果temp非0，則ret := ret + temp + 1
- 返回ret。
讓我們看下面的實現來更好地理解：
示例
#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
更新於：2020年5月4日
瀏覽量：172
廣告