数据结构
网络
关系数据库管理系统 (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
广告