最小の一意の単語の略語

Minimum Unique Word Abbreviation

トピック
'word'などの文字列には、次の略語が含まれています。

['word'、 '1ord'、 'w1rd'、 'wo1d'、 'wor1'、 '2rd'、 'w2d'、 'wo2'、 '1o1d'、 '1or1'、 'w1r1'、 '1o2'、 ' 2r1 '、' 3d '、' w3 '、' 4 ']
ディクショナリ内のターゲット文字列と文字列のセットを指定して、ディクショナリ内の文字列の略語と競合しないように、可能な限り最小の長さでこのターゲット文字列の略語を見つけます。

略語の各数字または文字は長さ= 1と見なされます。たとえば、略語「a32bc」の長さは4です。

注意：
以下の2番目の例に示すように複数の回答がある場合は、いずれか1つを返すことができます。
ターゲット文字列の長さ= m、辞書のサイズ= nと仮定します。 m≤21、n≤1000、およびlog2（n）+m≤20と仮定できます。
例：
'apple'、['blade']-> 'a4'（ '5'または '4e'は 'blade'と競合するため）

'apple'、['plain'、 'amber'、 'blade']-> '1p3'（他の有効な回答には 'ap3'、 'a3e'、 '2p2'、 '3le'、 '3l1'が含まれます）。

回答

class Solution { public int count_abbrlen(int abbr, int m) { // Consecutive 0's is a number, each 1 is a letter int len = 0 for(int i = 0 i > i) & 1 if(bit == 1) { len++ } else if(bit == 0 && (((abbr >> (i+1) & 1) == 1) || i == m -1)) { len++ } } return len } public boolean has_conlict(String target, String word, int abbr) { int m = target.length() for(int i = 0 i > i) & 1 if(bit == 0) continue if(target.charAt(m - i - 1) != word.charAt(m - i - 1)) return false } return true } public String generate_abbrstr(String target, int abbr) { int m = target.length() // Create abbr from binary string String sb = '' int num = 0 for(int k = 0 k > k) & 1 if(bit == 1) { if(num > 0) sb = Integer.toString(num) + sb sb = target.charAt(m - k - 1) + sb num = 0 } else { num++ } } if(num > 0) sb = Integer.toString(num) + sb return sb } public String minAbbreviation(String target, String[] dictionary) { int m = target.length(), n = dictionary.length // Try each possible length, from small to big one for(int len = 1 len <= m len++) { //System.out.println('len: ' + Integer.toString(len)) // For each length, enumerate all binary strings for(int i = 0 i < 2 << (m - 1) i++) { int abbr_len = count_abbrlen(i, m) if(abbr_len == len) { //System.out.println('i: ' + Integer.toBinaryString(i)) boolean conflict = false for(String word : dictionary) { if(word.length() != m) continue if(has_conlict(target, word, i)) { conflict = true break } } // If no conflict found between any word in dict and abbr i, generate a abbr of target using abbr i if(!conflict) { return generate_abbrstr(target, i) } } } } return '' } }