資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 中的單詞縮寫
假設我們有一個包含 n 個唯一字串的陣列，我們必須根據以下規則為每個單詞生成儘可能短的縮寫。
從第一個字元開始，然後是縮寫的字元數，最後是最後一個字元。
如果我們發現任何衝突，即多個單詞共享相同的縮寫，則可以使用更長的字首代替僅第一個字元，直到將單詞到縮寫的對映變得唯一。
當縮寫沒有使單詞變短時，則保留其原始形式。
因此，如果輸入類似於 ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]，則輸出將是
["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
為了解決這個問題，我們將遵循以下步驟：
定義一個節點結構，它具有 cnt 和一個包含 26 個子節點的陣列，最初所有子節點都是空的。
定義一個函式 freeNode()，它將接受 head 引數。
如果 head 為空，則：
返回
對於初始化 i := 0，當 i < 26 時，更新 (i 增加 1)，執行：
freeNode(head 的 child[i])
刪除 head
定義一個函式 insertNode()，它將接受 node 和 s 引數。
curr = node
對於初始化 i := 0，當 i < s 的大小，更新 (i 增加 1)，執行：
x := s[i]
如果 node 的 child[x - 'a'] 不為空，則
node 的 child[x - 'a'] := 一個新節點
node := node 的 child[x - 'a']
將 node 的 cnt 增加 1
定義一個函式 abbreviate()，它將接受 node 和 s 引數。
ret := 空字串
curr = node
對於初始化 i := 0，當 i < s 的大小，更新 (i 增加 1)，執行：
x := s[i]
curr := curr 的 child[x - 'a']
如果 curr 的 cnt 等於 1，則：
rem := s 的大小
ret := (如果 rem <= 1，則 s，否則 s 從索引 0 到 i 的子字串連線 rem 作為字串連線 s 的最後一個元素
退出迴圈
返回 ret
定義一個函式 wordsAbbreviation()，它將接受一個數組 dict。
n := dict 的大小
定義一個大小為 n 的陣列 ret
定義一個 map m
對於初始化 i := 0，當 i < n 時，更新 (i 增加 1)，執行：
word := dict[i]
rem := word 的大小 - 2
x := (如果 rem <= 1，則 word，否則 word 的第一個元素連線 rem 連線 word 的最後一個元素)
將 i 插入到 m[x] 的末尾
ret[i] := x
對於 m 中的每個鍵值對 it，執行：
如果 it 的值的長度 <= 1，則：
(it 增加 1)
忽略以下部分，跳到下一個迭代
head := 一個新節點
對於初始化 i := 0，當 i < it 的值的大小，更新 (i 增加 1)，執行：
idx := it 的 value[i]
insertNode(head, dict[idx])
對於初始化 i := 0，當 i < it 的值的大小，更新 (i 增加 1)，執行：
idx := it 的 value[i]
ret[idx] := abbreviate(head, dict[idx])
freeNode(head)
(it 增加 1)
返回 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;
}
struct Node{
int cnt;
Node* child[26];
Node(){
cnt = 0;
for(int i = 0; i < 26; i++)child[i] = NULL;
}
};
class Solution {
public:
void freeNode(Node* head){
if (!head)
return;
for (int i = 0; i < 26; i++) {
freeNode(head->child[i]);
}
delete head;
}
void insertNode(Node* node, string s){
Node* curr = node;
for (int i = 0; i < s.size(); i++) {
char x = s[i];
if (!node->child[x - 'a']) {
node->child[x - 'a'] = new Node();
}
node = node->child[x - 'a'];
node->cnt++;
}
}
string abbreviate(Node* node, string s){
string ret = "";
Node* curr = node;
for (int i = 0; i < s.size(); i++) {
char x = s[i];
curr = curr->child[x - 'a'];
if (curr->cnt == 1) {
int rem = s.size() - (i + 2);
ret = rem <= 1 ? s : s.substr(0, i + 1) + to_string(rem) + s.back();
break;
}
}
return ret;
}
vector<string> wordsAbbreviation(vector<string>& dict) {
int n = dict.size();
vector<string> ret(n);
map<string, vector<int> > m;
for (int i = 0; i < n; i++) {
string word = dict[i];
int rem = word.size() - 2;
string x = rem <= 1 ? word : word.front() + to_string(rem) + word.back();
m[x].push_back(i);
ret[i] = x;
}
Node* head;
map<string, vector<int> >::iterator it = m.begin();
while (it != m.end()) {
if (it->second.size() <= 1) {
it++;
continue;
}
head = new Node();
for (int i = 0; i < it->second.size(); i++) {
int idx = it->second[i];
insertNode(head, dict[idx]);
}
for (int i = 0; i < it->second.size(); i++) {
int idx = it->second[i];
ret[idx] = abbreviate(head, dict[idx]);
}
freeNode(head);
it++;
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"like","god","internal","me","internet","interval","intension","face","intrusion"};
print_vector(ob.wordsAbbreviation(v));
}輸入
{"like","god","internal","me","internet","interval","intension","face","intrusion"}輸出
[l2e, god, internal, me, i6t, interval, inte4n, f2e, intr4n, ]
831 次檢視
