C++で解く「最小の一意な単語の略語」問題 ― ビットマスクとDFSによる効率的なアプローチ

この記事では、C++を使って「最小の一意な単語の略語（Minimum Unique Word Abbreviation）」問題を解く方法を解説します。ビットマスクと深さ優先探索（DFS）を組み合わせた効率的なアルゴリズムの考え方と実装例を紹介します。

問題の概要

まず、文字列「word」には次のようなさまざまな略語が考えられます。

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

ここで、ターゲット文字列と、辞書として与えられる文字列の集合が入力として渡されます。求めるのは、辞書内のどの単語の略語とも衝突しない、できるだけ短いターゲット文字列の略語です。

略語の長さの数え方には注意が必要です。数字や英字はそれぞれ長さ1としてカウントされますが、連続する数字（例：「32」）は1つのまとまりとして数えます。したがって、例えば「a32bc」の長さは4になります（a ／ 32 ／ b ／ c の4要素）。

具体例を挙げます。入力が「apple」、辞書が ["blade"] の場合、出力は「a4」となります。「apple」を「a4」と略しても、「blade」のいかなる略語とも一致しないためです。

解法のステップ

この問題は、ビットマスクとDFS（深さ優先探索）を用いて、以下の手順で解きます。

1. 配列 dict を定義する
2. 関数 abbrLen(mask) を定義する：マスクに対応する略語の長さを計算します。
   • ret := n で初期化する
   • b := 3 から開始し、b < bn の間、b を1ビットずつ左シフトしながらループする
   • (mask AND b) == 0 のとき、ret を1減らす（連続して省略された2文字は1つの数字にまとめられるため）
   • ret を返す
3. 関数 dfs(bit, mask) を定義する
   • len := abbrLen(mask) を求める
   • len >= minLen の場合は、それ以上探索しても改善しないため処理を打ち切って戻る
   • match := true とする
   • dict 内の各 d について、(mask AND d) == 0 なら match := false としてループを抜ける
   • match が true の場合：minLen := len、minab := mask を更新する
   • そうでない場合：b := bit から b < bn の間、b を2倍しながらループし、(cand AND b) != 0 なら dfs(b*2, mask OR b) を再帰呼び出しする
4. メインメソッドでの処理
   • ret := 空文字列、n := ターゲットの長さ、bn := 2^n、cand := 0、minLen := 無限大 で初期化する
   • 辞書内の各 s について：
     • s の長さが n と異なる場合はスキップする
     • word := 0 とし、i = 0 から s の長さ未満まで、s[i] != target[i] なら word |= 2^i とする
     • word を dict の末尾に追加し、cand |= word を行う
   • dfs(1, 0) を呼び出す
   • i = 0 から n 未満の間：
     • (minab AND 2^i) != 0 なら、ret に target[i] を追加して i を1進める
     • そうでなければ、j := i とし、i < n かつ (minab AND 2^i) == 0 の間 i を進め、ret に (i − j) を連結する
   • ret を返す

実装例

理解を深めるために、以下のC++実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int n, cand, bn, minLen, minab;
    vector<int> dict;
    int abbrLen(int mask) {
        int ret = n;
        for (int b = 3; b < bn; b <<= 1) {
            if ((mask & b) == 0)
                ret--;
        }
        return ret;
    }
    void dfs(int bit, int mask) {
        int len = abbrLen(mask);
        if (len >= minLen)
            return;
        bool match = true;
        for (int d : dict) {
            if ((mask & d) == 0) {
                match = false;
                break;
            }
        }
        if (match) {
            minLen = len;
            minab = mask;
        }
        else {
            for (int b = bit; b < bn; b <<= 1) {
                if ((cand & b) != 0)
                    dfs(b << 1, mask | b);
            }
        }
    }
    string minAbbreviation(string target, vector<string> &dictionary) {
        string ret = "";
        n = target.size();
        bn = 1 << n;
        cand = 0;
        minLen = INT_MAX;
        for (string &s : dictionary) {
            if (s.size() != n)
                continue;
            int word = 0;
            for (int i = 0; i < s.size(); i++) {
                if (s[i] != target[i])
                    word |= (1 << i);
            }
            dict.push_back(word);
            cand |= word;
        }
        dfs(1, 0);
        for (int i = 0; i < n;) {
            if ((minab & (1 << i)) != 0) {
                ret += target[i];
                i++;
            }
            else {
                int j = i;
                while (i < n && (minab & (1 << i)) == 0)
                    i++;
                ret += to_string(i - j);
            }
        }
        return ret;
    }
};
main() {
    Solution ob;
    vector<string> v = {"blade"};
    cout << (ob.minAbbreviation("apple",v));
}

入力

"apple",{"blade"}

出力

a4

アルゴリズムのポイント

この解法の鍵となるアイデアを整理しておきましょう。

• ビットマスクによる状態管理：ターゲット文字列の各位置について、「文字を残す（ビットが立っている）」か「省略する（ビットが立っていない）」かをビットで表現します。
• 候補ビットへの絞り込み：cand は、辞書内の同じ長さの単語とターゲットが異なる文字位置の和集合です。衝突の回避に寄与するのはこのビットだけなので、探索範囲を大幅に絞り込めます。
• 枝刈り：現在のマスクで計算した略語長が既知の最小値以上であれば、それ以降の探索を即座に打ち切ります。
• 衝突判定：あるマスクについて、すべての辞書単語の差分マスク d との AND が非ゼロになれば、その略語はどの辞書単語の略語とも一致しないことが保証されます。