|
| 1 | +packagecom.fishercoder.solutions; |
| 2 | + |
| 3 | +importjava.util.Arrays; |
| 4 | +importjava.util.HashSet; |
| 5 | +importjava.util.List; |
| 6 | + |
| 7 | +/** |
| 8 | + * 527. Word Abbreviation |
| 9 | + * |
| 10 | + * Given an array of n distinct non-empty strings, you need to generate minimal possible abbreviations for every word following rules below. |
| 11 | +
|
| 12 | + Begin with the first character and then the number of characters abbreviated, which followed by the last character. |
| 13 | + If there are any conflict, that is more than one words share the same abbreviation, |
| 14 | + a longer prefix is used instead of only the first character until making the map |
| 15 | + from word to abbreviation become unique. |
| 16 | + In other words, a final abbreviation cannot map to more than one original words. |
| 17 | + If the abbreviation doesn't make the word shorter, then keep it as original. |
| 18 | +
|
| 19 | + Example: |
| 20 | + Input: ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"] |
| 21 | + Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"] |
| 22 | +
|
| 23 | + Note: |
| 24 | + Both n and the length of each word will not exceed 400. |
| 25 | + The length of each word is greater than 1. |
| 26 | + The words consist of lowercase English letters only. |
| 27 | + The return answers should be in the same order as the original array. |
| 28 | + */ |
| 29 | +publicclass_527 { |
| 30 | + |
| 31 | +/**reference: https://discuss.leetcode.com/topic/82613/really-simple-and-straightforward-java-solution*/ |
| 32 | +publicList<String>wordsAbbreviation(List<String>dict) { |
| 33 | +intlen =dict.size(); |
| 34 | +String[]ans =newString[len]; |
| 35 | +int[]prefix =newint[len]; |
| 36 | +for (inti =0;i <len;i++) { |
| 37 | +prefix[i] =1; |
| 38 | +ans[i] =abbreviate(dict.get(i),1);// make abbreviation for each string |
| 39 | + } |
| 40 | +for (inti =0;i <len;i++) { |
| 41 | +while (true) { |
| 42 | +HashSet<Integer>set =newHashSet<>(); |
| 43 | +for (intj =i +1;j <len;j++) { |
| 44 | +if (ans[j].equals(ans[i]))set.add(j);// check all strings with the same abbreviation |
| 45 | + } |
| 46 | +if (set.isEmpty())break; |
| 47 | +set.add(i); |
| 48 | +for (intk :set) |
| 49 | +ans[k] =abbreviate(dict.get(k), ++prefix[k]);// increase the prefix |
| 50 | + } |
| 51 | + } |
| 52 | +returnArrays.asList(ans); |
| 53 | + } |
| 54 | + |
| 55 | +privateStringabbreviate(Stringword,intk) { |
| 56 | +if (k +2 >=word.length()) { |
| 57 | +returnword; |
| 58 | + } |
| 59 | +StringBuilderstringBuilder =newStringBuilder(); |
| 60 | +stringBuilder.append(word.substring(0,k)); |
| 61 | +stringBuilder.append(word.length() -1 -k); |
| 62 | +stringBuilder.append(word.substring(word.length()-1)); |
| 63 | +returnstringBuilder.toString(); |
| 64 | + } |
| 65 | + |
| 66 | +publicstaticvoidmain(String...args) { |
| 67 | +_527test =new_527(); |
| 68 | +System.out.println(test.abbreviate("saaap",2)); |
| 69 | + } |
| 70 | +} |