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").
Tips:
这道题实际上是之前那两道Valid Word Abbreviation和Generalized Abbreviation的合体，我们的思路其实很简单，首先找出target的所有的单词缩写的形式，然后按照长度来排序，小的排前面，我们用优先队列来自动排序，里面存一个pair，保存单词缩写及其长度，然后我们从最短的单词缩写开始，跟dictionary中所有的单词一一进行验证，利用Valid Word Abbreviation中的方法，看其是否是合法的单词的缩写，如果是，说明有冲突，直接break，进行下一个单词缩写的验证。
Similar to the bit manipulation idea, I use "" to replace the a char in the target string. Then, we start with putting a string with all "**" which has length =1 into the heap. When pop, check whether it is an overlap with other words in the dictionary. If not, we get the result and return it. Otherwise, we generate the next abbr from current one by replacing "" with a char of the target string.
Code:
public class Solution {
class Abbr{
String abbr;
int len;
Abbr(String abbr, int len) {
this.abbr = abbr;
this.len = len;
}
}
public String minAbbreviation(String target, String[] dictionary) {
Set<String> visited = new HashSet();
PriorityQueue<Abbr> q = new PriorityQueue(1, new CompAbbr() );
int len=target.length();
String first = "";
for (int i=0; i<len; i++) first+="*";
q.offer(new Abbr(first, 1) );
while (! q.isEmpty() ) {
Abbr ab = q.poll();
String abbr = ab.abbr;
boolean conflict = false;
for (String word: dictionary) {
if ( (word.length() == len) && isConflict(abbr, word) ) {
conflict = true;
break;
}
}
if (conflict) {
generateAbbr(target, abbr, visited, q);
} else {
return NumAbbr(abbr);
}
}
return null;
}
int abbrLength(String abbr){
int ret = 0, star = 0;
for (char c: abbr.toCharArray()){
if (c >= 'a' && c <= 'z') {
ret += 1 + star;
star = 0;
} else if (c=='*'){
star = 1;
}
}
return ret+star;
}
class CompAbbr implements Comparator<Abbr> {
public int compare(Abbr s1, Abbr s2){
return Integer.compare( s1.len, s2.len );
}
}
void generateAbbr(String str, String abbr, Set<String> visited, PriorityQueue<Abbr> q){
char[] temp = abbr.toCharArray();
for (int i=0; i<temp.length;i++){
if (temp[i] == '*') {
temp[i] = str.charAt(i);
String next = new String(temp);
if (! visited.contains(next) ) {
q.offer( new Abbr(next, abbrLength(next) ) );
visited.add( next );
}
temp[i] = '*';
}
}
}
boolean isConflict(String abbr, String str){
for (int i=0; i<abbr.length(); i++){
if ( abbr.charAt(i) != '*' && str.charAt(i) != abbr.charAt(i) ) return false;
}
return true;
}
String NumAbbr(String abbr){
String ret="";
int count=0;
for (char c : abbr.toCharArray() ){
if (c >='a' && c <='z') {
if (count > 0) {
ret += count;
count=0;
}
ret+=c;
} else {
count++;
}
}
if (count > 0) ret += count;
return ret;
}
}
CPP:
class Solution {
public:
string minAbbreviation(string target, vector<string>& dictionary) {
if (dictionary.empty()) return to_string((int)target.size());
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> q;
q = generate(target);
while (!q.empty()) {
auto t = q.top(); q.pop();
bool no_conflict = true;
for (string word : dictionary) {
if (valid(word, t.second)) {
no_conflict = false;
break;
}
}
if (no_conflict) return t.second;
}
return "";
}
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> generate(string target) {
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> res;
for (int i = 0; i < pow(2, target.size()); ++i) {
string out = "";
int cnt = 0, size = 0;
for (int j = 0; j < target.size(); ++j) {
if ((i >> j) & 1) ++cnt;
else {
if (cnt != 0) {
out += to_string(cnt);
cnt = 0;
++size;
}
out += target[j];
++size;
}
}
if (cnt > 0) {
out += to_string(cnt);
++size;
}
res.push({size, out});
}
return res;
}
bool valid(string word, string abbr) {
int m = word.size(), n = abbr.size(), p = 0, cnt = 0;
for (int i = 0; i < abbr.size(); ++i) {
if (abbr[i] >= '0' && abbr[i] <= '9') {
if (cnt == 0 && abbr[i] == '0') return false;
cnt = 10 * cnt + abbr[i] - '0';
} else {
p += cnt;
if (p >= m || word[p++] != abbr[i]) return false;
cnt = 0;
}
}
return p + cnt == m;
}
};