Description

Submission

class Solution {
    string abbreviate(const string& str, int mask) {
        int n = str.length();
        int cnt = 0;   // number of continuous zero
        string ret;
        for(int i = 0; i < n; ++i) {
            if((mask>>i)&1) {
                if(cnt) {
                    ret += to_string(cnt);
                    cnt = 0;
                }
                ret.push_back(str[i]);
            } else {
                ++cnt;
            }
        }
        if(cnt) ret += to_string(cnt);
        return ret;
    }
public:
    string minAbbreviation(string target, vector<string>& dictionary) {
        int m = target.length();

        vector<string> dict;
        for(auto& word: dictionary) {
            if(target.length() == word.length()) {
                dict.push_back(word);
            }
        }

        if(dict.empty()) {
            return to_string(target.length());
        }

        int minLen = m;
        string ret = target;

        for(int i = 0; i < (1 << m); ++i) {
            bool flag = true;
            string abbr = abbreviate(target, i);
            for(auto& word: dict) {
                if(abbreviate(word, i) == abbr) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                if(abbr.length() < minLen) {
                    minLen = abbr.length();
                    ret = abbr;
                }
            }
        }

        return ret;
    }
};