320. Generalized Abbreviation

Write a function to generate the generalized abbreviations of a word.

Example:

Given word ="word", return the following list (order does not matter):

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

S： backtracking O(2^n) ?

从第0位开始每次选取0 - n个char转换为数字

    vector<string> generateAbbreviations(string word) {
        vector<string> result;
        getAbbr(word, 0, "", result);
        return result;
    }

    void getAbbr(string word, int start, string s, vector<string>& result) {
        if (start == word.size()) {
            result.push_back(s);
            return;
        }
        getAbbr(word, start + 1, s + word[start], result);
        if (start > 0 && isdigit(s.back())) return;  
        for(int i = start; i < word.size(); ++i) {
            getAbbr(word, i + 1, s + to_string(i - start + 1), result);
        }
    }

288. Unique Word Abbreviation

An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:

a) it                      --> it    (no abbreviation)
     1
b) d|o|g                   --> d1g
              1    1  1
     1---5----0----5--8
c) i|nternationalizatio|n  --> i18n
              1
     1---5----0
d) l|ocalizatio|n          --> l10nAssume you have a dictionary and given a word, 
                               find whether its abbreviation is unique in the dictionary. A word's 
                               abbreviation is unique if no other word from the dictionary has the 
                               same abbreviation.

Example:

Given dictionary = [ "deer", "door", "cake", "card" ]
isUnique("dear") -> 
false
isUnique("cart") -> 
true
isUnique("cane") -> 
false
isUnique("make") -> 
true

S：hashmap

理清题意：当word的abbr不存在dict中时，word unique； 当的abbr存在于dict中且只对应word一个单词时，为unique

class ValidWordAbbr {
public:
    ValidWordAbbr(vector<string> dictionary) {
        for (string s : dictionary) {
            string str = s.size() > 2? s[0] + to_string(s.size()) + s.back()  : s;
            abbrmap[str].insert(s);
        }
    }

    bool isUnique(string word) {
        string s = word.size() > 2? word[0] + to_string(word.size()) + word.back() : word;
        return abbrmap.find(s) == abbrmap.end() || abbrmap[s].count(word) == abbrmap[s].size();

    }
private:
    unordered_map<string, unordered_set<string>> abbrmap;
};

411. Minimum Unique Word Abbreviation

A string such as "word" contains the following abbreviations:

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

Given a target string and a set of strings in a dictionary, find an abbreviation of this target string with the smallest possible length such that it does not conflict with abbreviations of the strings in the dictionary.

Each number or letter in the abbreviation is considered length = 1. For example, the abbreviation "a32bc" has length = 4.

Note:

• In the case of multiple answers as shown in the second example below, you may return any one of them.
• Assume length of target string = m, and dictionary size = n. You may assume that m ≤ 21, n ≤ 1000, and log2(n) + m ≤ 20.

Examples

"apple", ["blade"] -> "a4" (because "5" or "4e" conflicts with "blade")

"apple", ["plain", "amber", "blade"] -> "1p3" (other valid answers include "ap3", "a3e", "2p2", "3le", "3l1").

S： bit manipulation + recursion

只考虑dictionary中长度与target相同的词语为candidate，因为要unique，需要保留target中和candidate不同的char，一个个比较candidate得到长为n的bitset，第i位不同置1，相同置0。只有candidate和target不同的char才是我们要考虑是否保留的，从最短的mask开始一个个尝试将bitset为1的target位置保留，直到mask & 所有candidate > 0，即每个candidate都有至少一个和target不同的char得到了保留

//wrong answer
class Solution {
public:
    string minAbbreviation(string target, vector<string>& dictionary) {
        n = target.size();
        difbits = 0;
        for (const string& s : dictionary) {
            if (s.size() == n) {  //loop all string with the same length as target
                int dif = 0;
                for (int i = 0; i < n; ++i) {
                    dif <<= 1;
                    if (s[i] != target[i]) {  //set bit of different char position to 1 
                         dif += 1;
                    }
                }
                candidates.push_back(dif);
                difbits |= dif; // 'or' candidate bits to get all bits we need to check
            }
        }
        int mask = 0, minlen = n;
        dfs(0, minlen, 0, mask);
        return getAbbr(target, mask);
    }

private:
    vector<int> candidates;
    int difbits;
    int n;
    void dfs(int bit, int& minlen, int curmask, int& minmask ) {
        int len = getLen(curmask);
        if (len >= minlen) return;
        bool isValid = true;
        for (int i : candidates) {
            if ((i & curmask) == 0) {
                isValid = false;
                break;
            }
        }
        if (isValid) {
            minlen = len;
            minmask = curmask;
        } else {
            for (; bit < n; ++bit) {
                if (difbits & (1 << bit)) dfs(bit + 1, minlen, curmask | (1 << bit), minmask);
            }
        }
    }

    int getLen(int mask) {
        int count = n;
        //mask will save space if there are at least two consecutive 0
        for (int i = 1, countmask = 3; i < n; ++i, countmask <<= 1) { 
            if ((countmask & mask) == 0) count--;
        }
        return count;
    }

    string getAbbr(string target, int mask) {
        string result = "";
        int count = 0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                if (count) {
                    result = to_string(count) + result;
                    count = 0;
                }
                result = target[n - 1 - i] + result;
            } else {
                count++;
            }
        }
        if (count) result = to_string(count) + result;
        return result;;
    }
};