Leetcode: Minimum Unique Word Abbreviation

发布时间:2017-3-30 16:55:36 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Leetcode: Minimum Unique Word Abbreviation ",主要涉及到Leetcode: Minimum Unique Word Abbreviation 方面的内容,对于Leetcode: 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").

Refer to https://discuss.leetcode.com/topic/61799/java-bit-mask-dfs-with-pruning

bit mask refer to http://bookshadow.com/weblog/2016/10/02/leetcode-minimum-unique-word-abbreviation/

1. The key idea of my solution is to preprocess the dictionary to transfer all the words to bit sequences (int):

比如apple 和 amper 字母相同设1,不同设0,所以得到10100

又比如target='apple',word='amble',则word的bitmask为10011

在这个过程中ignore与target长度不一样的,得到每个字典里面的bitmask,下面称呼它为mask,所以mask里为1的位表示与target字母相同

a p p l ea m b l e1 0 0 1 1

2. 开始缩写target单词,只不过我们不直接缩写成十进制数,而是先缩写成二进制,1表示保留字母,0表示替换为数字。下面称呼这个当前的缩写结果为curResult, 因为curResult由target缩写而来,所以curResult里为1的位与target字母相同

例如单词manipulation的缩写m2ip6n可以转化为100110000001

m a n i p u l a t i o nm  2  i p      6      n1 0 0 1 1 0 0 0 0 0 0 1

3. mask里为1的位表示与target字母相同, 同时curResult里为1的位也与target字母相同, 如果

 curResult & mask == curResult,

则说明curResult里为1的位子上,mask也一定是1,那么curResult也一定是mask所对应的那个string的一个缩写,所以这里conflict出现了,所以这个curResult要被skip掉

4. 在所有没有conflict的curResult里面,找到长度最短的一个,如何找到长度最短,可以在recursion里面维护一个当前curResult长度大小的变量,同时有一个变量保存最小长度用以更新

5. 最后将长度最短那个curResult(它目前只是一个二进制缩写),复原成十进制缩写

这是我做过最难的Bitmask的题了

  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 }

上一篇:linux下, 再次遇到使用thinkphp的模板标签时,报错used undefined function \Think\Template\simplexml_load_string() 是因为没有安装 php-xml包
下一篇:SecureCRT使用小技巧

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款