原題單詞縮寫
給出一組 n 個(gè)不同的非空字符串赎线，您需要按以下規(guī)則為每個(gè)單詞生成 最小 的縮寫。
- 從第一個(gè)字符開始糊饱，然后加上中間縮寫掉的字符的長(zhǎng)度垂寥，后跟最后一個(gè)字符。
- 如果有沖突另锋，就是多個(gè)單詞共享相同的縮寫滞项，使用較長(zhǎng)的前綴，而不是僅使用第一個(gè)字符夭坪，直到使單詞的縮寫的映射變?yōu)槲ㄒ弧?換句話說蓖扑，最終得到的縮寫不能映射到多個(gè)原始單詞。
- 如果縮寫不會(huì)使單詞更短台舱，則不進(jìn)行縮寫律杠，保持原樣。
審題
- 首先這題的有個(gè)地方說得不清楚竞惋，就是解決沖突的方式柜去。比如iabcx和idefx沖突了，因?yàn)榭s寫都是i3x,這時(shí)需要把這兩個(gè)都加長(zhǎng)前綴拆宛，變成ia2x和id2x嗓奢。重點(diǎn)在于兩者都變化。應(yīng)用到整個(gè)集合里浑厚，當(dāng)有其他單詞和你沖突時(shí)股耽，你就要增大前綴，知道沒有單詞和你沖突钳幅。
- 我看了下題目的標(biāo)簽物蝙，里有個(gè)排序，順著這個(gè)思路想了下：
只有后綴相同的單詞之前會(huì)可能沖突敢艰，因?yàn)楹缶Y一定保留
只有長(zhǎng)度相同的會(huì)沖突诬乞。證明：如果長(zhǎng)度不同的單詞縮寫到長(zhǎng)度相同，那么縮寫掉部分的長(zhǎng)度肯定不同钠导，那么中間的數(shù)字肯定不同震嫉，那么這兩個(gè)縮寫肯定不同，不會(huì)沖突牡属。
??所以只有長(zhǎng)度相同且后綴相同的單詞才會(huì)沖突票堵，所以把這些可能沖突的分到一個(gè)組里。
- 經(jīng)過2的處理逮栅，同一個(gè)組里悴势，都是有沖突隱患的單詞窗宇。對(duì)于某一個(gè)單詞，要保留多長(zhǎng)的前綴才可以呢瞳浦？它和組內(nèi)的其他單詞比較共同前綴，假如最長(zhǎng)共同前綴為k,那么它就保留到k+1,因?yàn)榈絢+1的這一段废士，所有其他的都會(huì)跟它呈現(xiàn)出不同叫潦。如果直接照著這個(gè)直接實(shí)現(xiàn)，復(fù)雜度是O(n^2),n是組內(nèi)的單詞個(gè)數(shù)官硝，有沒有辦法直接找到最長(zhǎng)共同前綴呢矗蕊？直接使用字符串的排序，字符串本身的比較方法是從前往后逐個(gè)比較字符氢架，所以具有更多共同前綴的單詞會(huì)貼到一起傻咖。
- 證明如下：
??假設(shè)排序后單詞k和k-1的共同前綴長(zhǎng)度是x,單詞k和k+1的共同長(zhǎng)度是y, 如果最長(zhǎng)共同前綴不是x或y,那么存在一個(gè)單詞t，它不在k的兩邊岖研，且共同前綴z滿足：z>x卿操，z>y。
??單詞k+1在k的后面孙援，且共同前綴是y,說明：k+1[y+1]>k[y+1];同理對(duì)于k-1有：k-1[x+1]<k[x+1]害淤。而z>x且z>y,那么這兩個(gè)式子對(duì)于t也是成立的，也就是在排序后t會(huì)在k-1和k+1之間拓售，而這時(shí)不可能的窥摄，所以出現(xiàn)錯(cuò)誤假設(shè)不成立，不存在這樣的t础淤。
??簡(jiǎn)單說崭放，公共前綴越長(zhǎng)，排序后越靠近鸽凶。所以每個(gè)單詞只需要取左右相鄰單詞的共同前綴作為參考即可币砂。
代碼：
//對(duì)單詞排序，按長(zhǎng)度玻侥、后綴和單詞本身的先后順序
//這樣長(zhǎng)度相同道伟、后綴相同的單詞會(huì)分到一起
bool wordPairCmp(pair<string, int>& wp1, pair<string, int> &wp2){
int result = (int)wp1.first.length()-(int)wp2.first.length();
if (result!=0) return result<0;
result = wp1.first.back()-wp2.first.back();
if (result!=0) return result<0;
return wp1.first.compare(wp2.first)<0;
}
//求共同前綴的長(zhǎng)度
inline int prefixLapCount(string &s1, string &s2){
int c = 0;
while (s1[c] == s2[c]) {
c++;
}
return c;
}
//把一個(gè)單詞按指定前綴長(zhǎng)度縮寫
inline void wordAbb(string &originalWord, int prefixCount){
int len = (int)originalWord.length();
int cut = len-prefixCount-1;
if (cut<=1) {
return;
}
int destLen = prefixCount+1+log10(cut)+1;
int preIdx = len-cut-2;
string abb(destLen,' ');
for (int i = 0; i<=preIdx; i++) {
abb[i] = originalWord[i];
}
abb[destLen-1] = originalWord.back();
//中間縮寫的數(shù)字部分，沒有使用atoi等方法而是直接實(shí)現(xiàn)使碾，效率會(huì)快很對(duì)
for (int i = destLen-2; i>preIdx; i--) {
abb[i] = cut%10+'0';
cut = cut/10;
}
originalWord = abb;
}
vector<string> wordsAbbreviation(vector<string> &dict) {
//使用pair的原因是為了記錄單詞在原數(shù)組里的索引位置蜜徽，這樣排序后，還可以再重置到輸入時(shí)的順序
vector<pair<string, int>> wordPairs;
int i = 0;
for (auto &w : dict){
wordPairs.push_back({w,i});
i++;
}
sort(wordPairs.begin(), wordPairs.end(), wordPairCmp);
int size = (int)wordPairs.size();
int preLapCount = 0; //和前一個(gè)重疊的字符個(gè)數(shù)
for (int i = 0; i<size; i++) {
int nextLapCount = 0;
//因?yàn)闆]有使用分組票摇，即沒有用多維數(shù)組拘鞋，而是單個(gè)數(shù)組，所以需要做前后判定矢门，長(zhǎng)度不同或者后綴不同盆色，則共同前綴就不考慮了灰蛙，直接是0.
//這里會(huì)影響效率，因?yàn)榇蟛糠直容^都是無意義的或者說跟排序的工作有重復(fù)
if (i<size-1 &&
wordPairs[i].first.length() == wordPairs[i+1].first.length() &&
wordPairs[i].first.back() == wordPairs[i+1].first.back()) {
nextLapCount = prefixLapCount(wordPairs[i].first, wordPairs[i+1].first);
}
wordAbb(wordPairs[i].first, max(preLapCount, nextLapCount)+1);
preLapCount = nextLapCount;
}
for (auto &p : wordPairs){
dict[p.second] = p.first;
}
return dict;
}
