public class Solution {
class Word implements Comparable<Word> {
String wd;
int idx;
Word(String word, int idx) {
this.wd = word; this.idx = idx;
}
public int compareTo(Word w) {
if (this.wd.length() == w.wd.length())
return this.wd.compareTo(w.wd);
return w.wd.length() - this.wd.length();
}
}
public List<String> wordsAbbreviation(List<String> dict) {
int n = dict.size();
Word[] words = new Word[n+1];
for(int i =0; i < n; i++) {
String word = dict.get(i);
words[i] = new Word(word.charAt(word.length()-1) + word, i);
}
words[n] = new Word("", n);
Arrays.sort(words);
int pref = 0;
for(int i = 0; i < n; i++) {
String w1 = words[i].wd, w2 = words[i+1].wd;
int cur = 0;
if (w1.length() == w2.length()) {
cur = commonPref(w1, w2);
}
String abbr = getAbbr(w1, Math.max(cur, pref));
pref = cur;
dict.set(words[i].idx, abbr.length() < w1.length()-1 ? abbr: w1.substring(1));
}
return dict;
}
private String getAbbr(String str, int pref) {
if (pref == 0) {
pref = 1;
}
int count = str.length() - pref - 2;
return str.substring(1, pref+1) + count + str.charAt(0);
}
private int commonPref(String s1, String s2) {
int pref = 0;
while(pref < s1.length()) {
if (s1.charAt(pref) != s2.charAt(pref))
return pref;
pref++;
}
return pref;
}
}
/*
Make abbreviation for each word.
Then, check each word, if there are some strings which have same abbreviation with it, increase the prefix.
*/
public class Solution {
public List<String> wordsAbbreviation(List<String> dict) {
int len=dict.size();
String[] ans=new String[len];
int[] prefix=new int[len];
for (int i=0;i<len;i++) {
prefix[i]=1;
ans[i]=makeAbbr(dict.get(i), 1); // make abbreviation for each string
}
for (int i=0;i<len;i++) {
while (true) {
HashSet<Integer> set=new HashSet<>();
for (int j=i+1;j<len;j++) {
if (ans[j].equals(ans[i])) set.add(j); // check all strings with the same abbreviation
}
if (set.isEmpty()) break;
set.add(i);
for (int k: set)
ans[k]=makeAbbr(dict.get(k), ++prefix[k]); // increase the prefix
}
}
return Arrays.asList(ans);
}
private String makeAbbr(String s, int k) {
if (k>=s.length()-2) return s;
StringBuilder builder=new StringBuilder();
builder.append(s.substring(0, k));
builder.append(s.length()-1-k);
builder.append(s.charAt(s.length()-1));
return builder.toString();
}
}