527. Word Abbreviation
given tableau уникальных строк words, return минимально возможные сокращения для каждого слова.
Правила сокращения строки следующие:
Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ.
Если более одного слова имеют одинаковое сокращение, выполните следующее:
Увеличьте префикс (символы в первой части) каждого из их сокращений на 1.
НаExemple, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"].
Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным.
В конце, если сокращение не сделало слово короче, оставьте его в исходном виде.
Exemple:
Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
C# solution
correspondant/originalpublic class Solution {
public IList<string> WordsAbbreviation(IList<string> words) {
int n = words.Count;
string[] ans = new string[n];
int[] prefix = new int[n];
for (int i = 0; i < n; ++i)
ans[i] = Abbrev(words[i], 0);
for (int i = 0; i < n; ++i) {
while (true) {
HashSet<int> dupes = new HashSet<int>();
for (int j = i + 1; j < n; ++j) {
if (ans[i] == ans[j])
dupes.Add(j);
}
if (dupes.Count == 0) break;
dupes.Add(i);
foreach (int k in dupes)
ans[k] = Abbrev(words[k], ++prefix[k]);
}
}
return ans.ToList();
}
private string Abbrev(string word, int i) {
int n = word.Length;
if (n - i <= 3) return word;
return word.Substring(0, i + 1) + (n - i - 2) + word[n - 1];
}
}C++ solution
brouillon automatique, à relire avant soumission#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public vector<string> WordsAbbreviation(vector<string> words) {
int n = words.size();
vector<string> ans = new string[n];
vector<int>& prefix = new int[n];
for (int i = 0; i < n; ++i)
ans[i] = Abbrev(words[i], 0);
for (int i = 0; i < n; ++i) {
while (true) {
HashSet<int> dupes = new HashSet<int>();
for (int j = i + 1; j < n; ++j) {
if (ans[i] == ans[j])
dupes.push_back(j);
}
if (dupes.size() == 0) break;
dupes.push_back(i);
foreach (int k in dupes)
ans[k] = Abbrev(words[k], ++prefix[k]);
}
}
return ans.ToList();
}
private string Abbrev(string word, int i) {
int n = word.size();
if (n - i <= 3) return word;
return word.Substring(0, i + 1) + (n - i - 2) + word[n - 1];
}
}Java solution
correspondant/originalclass Solution {
public List<String> wordsAbbreviation(List<String> words) {
int N = words.size();
String[] ans = new String[N];
int[] prefix = new int[N];
for (int i = 0; i < N; ++i)
ans[i] = abbrev(words.get(i), 0);
for (int i = 0; i < N; ++i) {
while (true) {
Set<Integer> dupes = new HashSet();
for (int j = i+1; j < N; ++j)
if (ans[i].equals(ans[j]))
dupes.add(j);
if (dupes.isEmpty()) break;
dupes.add(i);
for (int k: dupes)
ans[k] = abbrev(words.get(k), ++prefix[k]);
}
}
return Arrays.asList(ans);
}
public String abbrev(String word, int i) {
int N = word.length();
if (N - i <= 3) return word;
return word.substring(0, i+1) + (N - i - 2) + word.charAt(N-1);
}
}JavaScript solution
correspondant/originalvar wordsAbbreviation = function(words) {
const n = words.length;
const ans = new Array(n).fill("");
const prefix = new Array(n).fill(0);
for (let i = 0; i < n; ++i) {
ans[i] = abbrev(words[i], 0);
}
for (let i = 0; i < n; ++i) {
while (true) {
const dupes = new Set();
for (let j = i + 1; j < n; ++j) {
if (ans[i] === ans[j]) {
dupes.add(j);
}
}
if (dupes.size === 0) break;
dupes.add(i);
for (const k of dupes) {
ans[k] = abbrev(words[k], ++prefix[k]);
}
}
}
return ans;
};
function abbrev(word, i) {
const n = word.length;
if (n - i <= 3) return word;
return word.slice(0, i + 1) + (n - i - 2) + word.slice(-1);
}Python solution
correspondant/originalclass Solution:
def wordsAbbreviation(self, words: List[str]) -> List[str]:
n = len(words)
ans = [self.abbrev(word, 0) for word in words]
prefix = [0] * n
for i in range(n):
while True:
dupes = set()
for j in range(i + 1, n):
if ans[i] == ans[j]:
dupes.add(j)
if not dupes:
break
dupes.add(i)
for k in dupes:
prefix[k] += 1
ans[k] = self.abbrev(words[k], prefix[k])
return ans
def abbrev(self, word: str, i: int) -> str:
n = len(word)
if n - i <= 3:
return word
return word[:i + 1] + str(n - i - 2) + word[-1]Go solution
correspondant/originalfunc wordsAbbreviation(words []string) []string {
n := len(words)
ans := make([]string, n)
prefix := make([]int, n)
for i := 0; i < n; i++ {
ans[i] = abbrev(words[i], 0)
}
for i := 0; i < n; i++ {
for {
dupes := make(map[int]bool)
for j := i + 1; j < n; j++ {
if ans[i] == ans[j] {
dupes[j] = true
}
}
if len(dupes) == 0 {
break
}
dupes[i] = true
for k := range dupes {
prefix[k]++
ans[k] = abbrev(words[k], prefix[k])
}
}
}
return ans
}
func abbrev(word string, i int) string {
n := len(word)
if n-i <= 3 {
return word
}
return word[:i+1] + fmt.Sprint(n-i-2) + word[n-1:]
}Algorithm
Инициализация и создание начальных сокращений:
Создайте tableau для хранения сокращений и tableau для отслеживания длины префикса каждого слова.
Для каждого слова создайте начальное сокращение с использованием первого символа, количества символов между первым и последним символом и последнего символа.
Обработка коллизий:
Для каждого слова проверьте, не совпадает ли его сокращение с уже существующими сокращениями.
Если сокращение не уникально, увеличьте длину префикса и повторите проверку.
Возврат результата:
return окончательные сокращения для каждого слова, убедившись, что они минимально возможны и уникальны.
😎
Vacancies for this task
offres actives with overlapping task tags are affichés.