## Word Abbreviation      ## Approach 1: Brute Force

• Time:O((\Sigma |\texttt{words[i]}|)^2)
• Space:O(\Sigma |\texttt{words[i]}|)

## C++

``````class Solution {
public:
vector<string> wordsAbbreviation(vector<string>& words) {
const int n = words.size();
vector<string> ans;
// prefix[i] := ans[i] takes words[i][0..prefix[i]]
vector<int> prefix(n);

for (const string& word : words)
ans.push_back(getAbbrev(word, 0));

for (int i = 0; i < n; ++i) {
while (true) {
vector<int> dupeIndices;
for (int j = i + 1; j < n; ++j)
if (ans[i] == ans[j])
dupeIndices.push_back(j);
if (dupeIndices.empty())
break;
dupeIndices.push_back(i);
for (const int index : dupeIndices)
ans[index] = getAbbrev(words[index], ++prefix[index]);
}
}

return ans;
}

private:
string getAbbrev(const string& s, int prefixIndex) {
const int n = s.length();
const int num = n - (prefixIndex + 1) - 1;
const int numLength = num < 10 ? 1 : num < 100 ? 2 : 3;
const int abbrevLength = (prefixIndex + 1) + numLength + 1;
if (abbrevLength >= n)
return s;
return s.substr(0, prefixIndex + 1) + to_string(num) + s.back();
}
};
``````

## JAVA

``````class Solution {
public List<String> wordsAbbreviation(List<String> words) {
final int n = words.size();
List<String> ans = new ArrayList<>();
// prefix[i] := ans[i] takes words[i][0..prefix[i]]
int[] prefix = new int[n];

for (int i = 0; i < n; ++i)

for (int i = 0; i < n; ++i)
while (true) {
List<Integer> dupeIndices = new ArrayList<>();
for (int j = i + 1; j < n; ++j)
if (ans.get(i).equals(ans.get(j)))
if (dupeIndices.isEmpty())
break;
for (final int dupeIndex : dupeIndices)
ans.set(dupeIndex, getAbbrev(words.get(dupeIndex), ++prefix[dupeIndex]));
}

return ans;
}

private String getAbbrev(final String s, int prefixIndex) {
final int n = s.length();
final int num = n - (prefixIndex + 1) - 1;
final int numLength = num < 10 ? 1 : num < 100 ? 2 : 3;
final int abbrevLength = (prefixIndex + 1) + numLength + 1;
if (abbrevLength >= n)
return s;
return s.substring(0, prefixIndex + 1) + num + s.charAt(n - 1);
}
}
``````

## Python

``````class Solution:
def wordsAbbreviation(self, words: List[str]) -> List[str]:
n = len(words)

def getAbbrev(s: str, prefixIndex: int) -> str:
n = len(s)
num = n - (prefixIndex + 1) - 1
numLength = 1 if num < 10 else (2 if num < 100 else 3)
abbrevLength = (prefixIndex + 1) + numLength + 1
if abbrevLength >= n:
return s
return s[:prefixIndex + 1] + str(num) + s[-1]

ans = [getAbbrev(word, 0) for word in words]
# prefix[i] := ans[i] takes words[i][0..prefix[i]]
prefix =  * n

for i in range(n):
while True:
dupeIndices = []
for j in range(i + 1, n):
if ans[i] == ans[j]:
dupeIndices.append(j)
if not dupeIndices:
break
dupeIndices.append(i)
for index in dupeIndices:
prefix[index] += 1
ans[index] = getAbbrev(words[index], prefix[index])

return ans
``````

## Approach 2: Group + Least Common Prefix

• Time:O(\Sigma |\texttt{words[i]}|\log\Sigma |\texttt{words[i]}|)
• Space:O(\Sigma |\texttt{words[i]}|)

## C++

``````struct IndexedWord {
string word;
int index;
IndexedWord(const string& word, int index) : word(word), index(index) {}
};

class Solution {
public:
vector<string> wordsAbbreviation(vector<string>& words) {
const int n = words.size();
vector<string> ans(n);
unordered_map<string, vector<IndexedWord>> abbrevToIndexedWords;

for (int i = 0; i < n; ++i) {
const string abbrev = getAbbrev(words[i], 0);
abbrevToIndexedWords[abbrev].emplace_back(words[i], i);
}

for (auto& [_, indexedWords] : abbrevToIndexedWords) {
sort(begin(indexedWords), end(indexedWords),
[](const auto& a, const auto& b) { return a.word < b.word; });
vector<int> lcp(indexedWords.size());
for (int i = 1; i < indexedWords.size(); ++i) {
const int k =
longestCommonPrefix(indexedWords[i - 1].word, indexedWords[i].word);
lcp[i - 1] = max(lcp[i - 1], k);
lcp[i] = k;
}
for (int i = 0; i < indexedWords.size(); ++i)
ans[indexedWords[i].index] = getAbbrev(indexedWords[i].word, lcp[i]);
}

return ans;
}

private:
string getAbbrev(const string& s, int prefixIndex) {
const int n = s.length();
const int num = n - (prefixIndex + 1) - 1;
const int numLength = num < 10 ? 1 : num < 100 ? 2 : 3;
const int abbrevLength = (prefixIndex + 1) + numLength + 1;
if (abbrevLength >= n)
return s;
return s.substr(0, prefixIndex + 1) + to_string(num) + s.back();
}

int longestCommonPrefix(const string& s1, const string& s2) {
int i = 0;
while (i < s1.length() && i < s2.length() && s1[i] == s2[i])
++i;
return i;
}
};
``````

## JAVA

``````class IndexedWord {
public String word;
public int index;
public IndexedWord(final String word, int index) {
this.word = word;
this.index = index;
}
}

class Solution {
public List<String> wordsAbbreviation(List<String> words) {
String[] ans = new String[words.size()];
Map<String, List<IndexedWord>> abbrevToIndexedWords = new HashMap<>();

for (int i = 0; i < words.size(); ++i) {
final String abbrev = getAbbrev(words.get(i), 0);
abbrevToIndexedWords.putIfAbsent(abbrev, new ArrayList<>());
}

for (var indexedWords : abbrevToIndexedWords.values()) {
Collections.sort(indexedWords, (a, b) -> a.word.compareTo(b.word));
int[] lcp = new int[indexedWords.size()];
for (int i = 1; i < indexedWords.size(); ++i) {
final int k = longestCommonPrefix(indexedWords.get(i - 1).word, indexedWords.get(i).word);
lcp[i - 1] = Math.max(lcp[i - 1], k);
lcp[i] = k;
}
for (int i = 0; i < indexedWords.size(); ++i)
ans[indexedWords.get(i).index] = getAbbrev(indexedWords.get(i).word, lcp[i]);
}

return Arrays.asList(ans);
}

private String getAbbrev(final String s, int prefixIndex) {
final int n = s.length();
final int num = n - (prefixIndex + 1) - 1;
final int numLength = num < 10 ? 1 : num < 100 ? 2 : 3;
final int abbrevLength = (prefixIndex + 1) + numLength + 1;
if (abbrevLength >= n)
return s;
return s.substring(0, prefixIndex + 1) + num + s.charAt(n - 1);
}

private int longestCommonPrefix(final String s1, final String s2) {
int i = 0;
while (i < s1.length() && i < s2.length() && s1.charAt(i) == s2.charAt(i))
++i;
return i;
}
}
``````

## Python

``````class IndexedWord:
def __init__(self, word: str, index: int):
self.word = word
self.index = index

class Solution:
def wordsAbbreviation(self, words: List[str]) -> List[str]:
n = len(words)
ans = [''] * n

def getAbbrev(s: str, prefixIndex: int) -> str:
n = len(s)
num = n - (prefixIndex + 1) - 1
numLength = 1 if num < 10 else (2 if num < 100 else 3)
abbrevLength = (prefixIndex + 1) + numLength + 1
if abbrevLength >= n:
return s
return s[:prefixIndex + 1] + str(num) + s[-1]

abbrevToIndexedWords = defaultdict(list)

for i, word in enumerate(words):
abbrev = getAbbrev(word, 0)
abbrevToIndexedWords[abbrev].append(IndexedWord(word, i))

def longestCommonPrefix(s1: str, s2: str) -> int:
i = 0
while i < len(s1) and i < len(s2) and s1[i] == s2[i]:
i += 1
return i

for indexedWords in abbrevToIndexedWords.values():
indexedWords.sort(key=lambda x: x.word)
lcp =  * len(indexedWords)
for i, (a, b) in enumerate(zip(indexedWords, indexedWords[1:])):
k = longestCommonPrefix(a.word, b.word)
lcp[i] = max(lcp[i], k)
lcp[i + 1] = k
for iw, l in zip(indexedWords, lcp):
ans[iw.index] = getAbbrev(iw.word, l)

return ans
``````

## Approach 3: Group + Trie

• Time:O(\Sigma |\texttt{words[i]}|)
• Space:O(\Sigma |\texttt{words[i]}|)

## C++

``````struct IndexedWord {
string word;
int index;
IndexedWord(const string& word, int index) : word(word), index(index) {}
};

struct TrieNode {
vector<TrieNode*> children;
int count = 0;
TrieNode() : children(26) {}
~TrieNode() {
for (TrieNode* child : children)
delete child;
}
};

class Solution {
public:
vector<string> wordsAbbreviation(vector<string>& words) {
const int n = words.size();
vector<string> ans(n);
unordered_map<string, vector<IndexedWord>> abbrevToIndexedWords;

for (int i = 0; i < n; ++i) {
const string abbrev = getAbbrev(words[i], 0);
abbrevToIndexedWords[abbrev].emplace_back(words[i], i);
}

for (auto& [_, indexedWords] : abbrevToIndexedWords) {
TrieNode root;
for (const auto& iw : indexedWords)
insertWord(&root, iw.word);
for (const auto& iw : indexedWords) {
const int index = firstUniqueIndex(&root, iw.word);
ans[iw.index] = getAbbrev(iw.word, index);
}
}

return ans;
}

private:
string getAbbrev(const string& s, int prefixIndex) {
const int n = s.length();
const int num = n - (prefixIndex + 1) - 1;
const int numLength = num < 10 ? 1 : num < 100 ? 2 : 3;
const int abbrevLength = (prefixIndex + 1) + numLength + 1;
if (abbrevLength >= n)
return s;
return s.substr(0, prefixIndex + 1) + to_string(num) + s.back();
}

void insertWord(TrieNode* root, const string& word) {
TrieNode* node = root;
for (const char c : word) {
if (!node->children[c - 'a'])
node->children[c - 'a'] = new TrieNode;
node = node->children[c - 'a'];
++node->count;
}
}

int firstUniqueIndex(TrieNode* root, const string& word) {
TrieNode* node = root;
for (int i = 0; i < word.length(); ++i) {
node = node->children[word[i] - 'a'];
if (node->count == 1)
return i;
}
return word.length();
}
};
``````

## JAVA

``````class IndexedWord {
public String word;
public int index;
public IndexedWord(final String word, int index) {
this.word = word;
this.index = index;
}
}

class TrieNode {
public TrieNode[] children = new TrieNode;
public int count = 0;
}

class Solution {
public List<String> wordsAbbreviation(List<String> words) {
String[] ans = new String[words.size()];
Map<String, List<IndexedWord>> abbrevToIndexedWords = new HashMap<>();

for (int i = 0; i < words.size(); ++i) {
final String abbrev = getAbbrev(words.get(i), 0);
abbrevToIndexedWords.putIfAbsent(abbrev, new ArrayList<>());
}

for (List<IndexedWord> indexedWords : abbrevToIndexedWords.values()) {
TrieNode root = new TrieNode();
for (IndexedWord iw : indexedWords)
insertWord(root, iw.word);
for (IndexedWord iw : indexedWords) {
final int index = firstUniqueIndex(root, iw.word);
ans[iw.index] = getAbbrev(iw.word, index);
}
}

return Arrays.asList(ans);
}

private String getAbbrev(final String s, int prefixIndex) {
final int n = s.length();
final int num = n - (prefixIndex + 1) - 1;
final int numLength = num < 10 ? 1 : num < 100 ? 2 : 3;
final int abbrevLength = (prefixIndex + 1) + numLength + 1;
if (abbrevLength >= n)
return s;
return s.substring(0, prefixIndex + 1) + num + s.charAt(n - 1);
}

private void insertWord(TrieNode root, final String word) {
TrieNode node = root;
for (final char c : word.toCharArray()) {
if (node.children[c - 'a'] == null)
node.children[c - 'a'] = new TrieNode();
node = node.children[c - 'a'];
++node.count;
}
}

private int firstUniqueIndex(TrieNode root, final String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); ++i) {
node = node.children[word.charAt(i) - 'a'];
if (node.count == 1)
return i;
}
return word.length();
}
}
``````

## Python

``````class IndexedWord:
def __init__(self, word: str, index: int):
self.word = word
self.index = index

class TrieNode:
def __init__(self):
self.children: Dict[str, TrieNode] = defaultdict(TrieNode)
self.count = 0

class Solution:
def wordsAbbreviation(self, words: List[str]) -> List[str]:
n = len(words)
ans = [''] * n

def getAbbrev(s: str, prefixIndex: int) -> str:
n = len(s)
num = n - (prefixIndex + 1) - 1
numLength = 1 if num < 10 else (2 if num < 100 else 3)
abbrevLength = (prefixIndex + 1) + numLength + 1
if abbrevLength >= n:
return s
return s[:prefixIndex + 1] + str(num) + s[-1]

abbrevToIndexedWords = defaultdict(list)

for i, word in enumerate(words):
abbrev = getAbbrev(word, 0)
abbrevToIndexedWords[abbrev].append(IndexedWord(word, i))

def insertWord(root: Optional[TrieNode], word: str) -> None:
node = root
for c in word:
if not node.children[c]:
node.children[c] = TrieNode()
node = node.children[c]
node.count += 1

def firstUniqueIndex(root: Optional[TrieNode], word: str) -> None:
node = root
for i, c in enumerate(word):
node = node.children[c]
if node.count == 1:
return i
return len(word)

for indexedWords in abbrevToIndexedWords.values():
root = TrieNode()
for iw in indexedWords:
insertWord(root, iw.word)
for iw in indexedWords:
index = firstUniqueIndex(root, iw.word)
ans[iw.index] = getAbbrev(iw.word, index)

return ans
``````