アルゴリズム:単語の略語

原題単語の略語
n個の異なる非空文字列のセットを指定します.以下のルールで単語ごとに最小の略語を生成する必要があります.

最初の文字から始まり、中間省略文字の長さを加えて最後の文字に続く.

競合がある場合は、複数の単語が同じ略語を共有し、単語の略語のマッピングが一意になるまで、最初の文字だけを使用するのではなく、長い接頭辞を使用します.すなわち,最終的に得られた略語は複数の元の単語にマッピングできない.

略語が単語を短くしない場合は、略語は行わず、そのままにします.

問題を調べる

まずこの問題のあるところははっきり言えないが、衝突を解決する方法だ.例えばiabcxとidefxが衝突した場合、略語はi 3 xなので、この2つを接頭辞を長くしてia 2 xとid 2 xにする必要があります.ポイントは両方が変化することです.コレクション全体に適用し、他の単語があなたと衝突している場合は、接頭辞を大きくして、単語があなたと衝突していないことを知っています.

私はテーマのラベルを見て、中にソートがあって、この考えに沿って考えました:

接尾辞は同じ単語だけが衝突する可能性があります.接尾辞は

を保持する必要があるからです.

長さが同じだけ衝突します.証明:長さの異なる単語を長さが同じに略すと、略す部分の長さが異なるに違いない.中間の数字が異なるに違いない.この2つの略語は異なるに違いない.衝突しない.

  だから長さが同じで接尾辞が同じ単語だけが衝突するので、これらの衝突する可能性のあるものを1つのグループに分けます.

は2の処理を経て、同じグループの中で、衝突の危険性のある単語です.ある単語について、どのくらいの接頭辞を残しておけばいいですか?グループ内の他の単語と共通接頭辞を比較し、最も長い共通接頭辞がkであれば、k+1まで保持されます.k+1までのセグメントでは、他のすべてが異なるためです.これをそのまま実現すれば複雑度はO(n^2)、nはグループ内の単語の個数で、最長共通接頭辞を直接見つけることができますか?文字列のソートを直接使用すると、文字列自体の比較方法は、行き先から文字を1つずつ比較するので、より共通の接頭辞を持つ単語が貼り付けられます.

証明は以下の通り:

  ソート後の単語kとk−1の共通接頭辞長はxであり、単語kとk+1の共通長はyであり、最長共通接頭辞がxまたはyでない場合、kの両側になく、共通接頭辞zが:z>x、z>yを満たす単語tが存在すると仮定する.
  単語k+1はkの後ろにあり、共通接頭辞はyであり、説明:k+1[y+1]>k[y+1];同様にk−1に対してk−1[x+1]xかつz>yがある場合、この2つの式はtに対しても成立し、すなわちソート後にtがk−1とk+1の間にあるが、この場合は不可能であるため、誤った仮定が成立せず、このようなtは存在しない.
単純に言えば、共通接頭辞が長ければ長いほど、ソート後に近づく.したがって,各単語は左右隣接する単語の共通接頭辞を参考にするだけでよい.
コード:

//     ，   、            
//      、            
bool wordPairCmp(pair& wp1, pair &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;
}

//        
inline int prefixLapCount(string &s1, string &s2){
    int c = 0;
    while (s1[c] == s2[c]) {
        c++;
    }
    return c;
}

//              
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();
    
    //         ，    atoi         ，      
    for (int i = destLen-2; i>preIdx; i--) {
        abb[i] = cut%10+'0';
        cut = cut/10;
    }
    
    originalWord = abb;
}

vector wordsAbbreviation(vector &dict) {
    
    //  pair                    ，     ，             
    vector> 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; //           
    for (int i = 0; i