C++で単語の最短エンコーディングを求める方法(トライ木活用)

単語のリストが与えられたとき、参照文字列 S とインデックスのリスト A を組み合わせることで、それらをエンコードできます。例えば、単語リストが ["time", "me", "bell"] の場合、S = "time#bell#"、indexes = [0, 2, 5] のように表現できます。各インデックスの位置から読み始め、"#" 記号に到達するまで読み進めると、元の単語を復元できる仕組みです。

ここでの課題は、与えられたすべての単語をエンコードできる最短の参照文字列 S の長さを求めることです。上記の例では、答えは 10 となります。

解法のアプローチ

この問題は、トライ木(Trie)を活用すると効率的に解けます。最大のポイントは、単語を「末尾から」トライ木に登録していく点です。具体的な手順は以下の通りです。

• insertNode メソッドを定義します。引数としてヘッドノード head と文字列 s を受け取ります。
• curr := head、flag := false と初期化します。
• i を s のサイズ − 1 から 0 まで逆順にループします。
  • x := s[i]
  • curr の m[x] が null の場合、flag := true とし、新しいノードを作成して curr の m[x] に格納します。
  • curr := curr の m[x] と更新します。
• flag が true なら s のサイズを返し、それ以外は 0 を返します。
• main メソッドでは以下を実行します。
• ret := 0、head := 新しいノード
• words 配列を文字列の長さの降順でソートします。
• n := words のサイズ
• i を 0 から n − 1 までループします。
  • temp := insertNode(head, words[i])
  • temp が 0 以外の場合、ret := ret + temp + 1 とします。
• ret を返します。

長い単語から先に処理することで、ある単語が別の単語の接尾辞(サフィックス)である場合には新しいノードが作られず、その分の文字数は加算されません。つまり、エンコードに本当に必要な文字だけを正確に数えられるのです。さらに、各単語の終端には区切り文字 "#" が 1 文字必要なため、temp + 1 を合計に加えています。

以下の実装例を見ると、より理解が深まるでしょう。

実装例(C++)

#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