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").

  1 public class Solution {
  2     private int minLen;
  3     private int result;
  4     
  5     public String minAbbreviation(String target, String[] dictionary) {
  6         // only keep words whose length == target in new dict, then compute their bit masks
  7         Set<Integer> maskSet = new HashSet<>();
  8         for(String s: dictionary){
  9             if(target.length() == s.length()){
 10                 maskSet.add(getBitMask(s,target));
 11             }
 12         }
 13     
 14         // dfs with pruning
 15         minLen = target.length()+1;
 16         result = -1;
 17     
 18         dfs(target,maskSet,0,0,0);
 19     
 20         if(minLen > target.length()){
 21             return "";
 22         }
 23     
 24         // convert result to word
 25         int zeroCnt = 0;
 26         String res = "";
 27         for (int i = target.length()-1; i>=0; i--) {
 28             //遇到0要累加连续零个数,遇到1填原char
 29             int digit = (result & 1);
 30             if(digit == 0){
 31                 ++zeroCnt;
 32             } else {
 33                 if(zeroCnt > 0){
 34                     res = zeroCnt + res;
 35                     zeroCnt =0;
 36                 }
 37                 res = target.charAt(i) + res;
 38             }
 39             result >>= 1;
 40         }
 41         if(zeroCnt > 0) res = zeroCnt + res;
 42         return res;
 43     }
 44     
 45     /**
 46      *
 47      * @param target
 48      * @param maskSet masks of words in dict
 49      * @param start idx at target
 50      * @param curLen current abbr‘s length
 51      */
 52     private void dfs(String target,Set<Integer> maskSet,int start,int curLen,int curResult){
 53         // pruning, no need to continue, already not min length
 54         if(curLen >= minLen) return;
 55     
 56         if(start == target.length()){
 57             // check whether curResult mask conflicts with words in dict
 58             for(int mask:maskSet){
 59                 /**
 60                  * 单词manipulation的缩写m2ip6n可以转化为100110000001
 61                  *  m a n i p u l a t i o n
 62                     m  2  i p      6      n
 63                     1 0 0 1 1 0 0 0 0 0 0 1
 64                  * 0代表随意不care,如果这个mask和dict中某个mask的所有1重合代表在意的位置完全相同,
 65                  * 说明这个mask和dict中那个词冲突
 66                  * 我们要找的是不冲突的mask
 67                  */
 68                 if((curResult & mask) == curResult){
 69                     return; // conflict
 70                 }
 71             }
 72             // no conflict happens, can use
 73             if(minLen > curLen){
 74                 minLen = curLen;
 75                 result = curResult;
 76             }
 77             return;
 78         }
 79     
 80         // case 1: replace chars from start in target with number
 81         for (int i = start; i < target.length(); i++) {
 82             //被replace掉的char位置由0代替所以是curResult<<(i+1-start),没replace掉的这里不管,我们只管到i,之后的由backtrack内决定
 83             //注意:不允许word => w11d这种用数字代替但含义不同
 84             if(curLen == 0 || (curResult &1) == 1){
 85                 //后者即上一次是保留了字母
 86                 dfs(target,maskSet,i+1,curLen+1,curResult<<(i+1-start));
 87             }
 88         }
 89     
 90         // case 2: no replace from start (curResult << 1)+1代表新的这位保留了char,所以是加一
 91         dfs(target,maskSet,start+1,curLen+1,(curResult << 1)+1);
 92     }
 93     
 94     // 比如apple 和 amper 字母相同设1,不同设0,所以得到10100
 95     private int getBitMask(String s1,String s2){
 96         int mask = 0;
 97         for (int i = 0; i < s1.length(); i++) {
 98             mask <<= 1;
 99             if(s1.charAt(i) == s2.charAt(i)){
100                 mask += 1;
101             }
102         }
103         return mask;
104     }
105 }