Given an array of n distinct non-empty strings, you need to generate minimal possible abbreviations for every word following rules below.
- Begin with the first character and then the number of characters abbreviated, which followed by the last character.
- If there are any conflict, that is more than one words share the same abbreviation, a longer prefix is used instead of only the first character until making the map from word to abbreviation become unique. In other words, a final abbreviation cannot map to more than one original words.
- If the abbreviation doesn't make the word shorter, then keep it as original.
Example:
Input: ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"] Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
- Both n and the length of each word will not exceed 400.
- The length of each word is greater than 1.
- The words consist of lowercase English letters only.
- The return answers should be in the same order as the original array.
又又又是一道题意模糊。仔细看给的例子,"internal, interval" 不会变成"i6l, in5l"。
再考虑这个例子:
"["abcdefg","abccefg","abcckkg"]" - > ["abcd2g","abccefg","abcckkg"]
["aabacd","aabbcd","aabbad"] -> ["aabacd","aabbcd","aabbad"]
ToDo ref: https://leetcode.com/problems/word-abbreviation/solution/
Solution #1, brute force
O(n ^ 2), n为dict大小
class Solution { public List<String> wordsAbbreviation(List<String> dict) { int n = dict.size(); int[] prefix = new int[n]; String[] rt = new String[n]; for (int i = 0; i < n; i++) { prefix[i] = 1; rt[i] = abbre(dict.get(i), 1); } for (int i = 0; i < n; i++) { String s = rt[i]; while (true) { List<Integer> dup = new ArrayList<>(); for (int j = i + 1; j < n; j++) { if (rt[j].equals(rt[i])) { dup.add(j); } } if (dup.size() == 0) break; dup.add(i); for (int d : dup) { rt[d] = abbre(dict.get(d), prefix[d]); prefix[d]++; } } } return Arrays.asList(rt); } private String abbre(String s, int i) { if (s.length() - i < 3) return s; StringBuilder rt = new StringBuilder(); rt.append(s.substring(0, i)); rt.append(s.length() - 1 - i); rt.append(s.charAt(s.length() - 1)); return rt.toString(); } }
No comments:
Post a Comment