| comments | difficulty | edit_url | tags | |||||
|---|---|---|---|---|---|---|---|---|
true |
Hard |
|
Given an array of distinct strings words, return the minimal possible abbreviations for every word.
The following are the rules for a string abbreviation:
- The initial abbreviation for each word is: the first character, then the number of characters in between, followed by the last character.
- If more than one word shares the same abbreviation, then perform the following operation:
- Increase the prefix (characters in the first part) of each of their abbreviations by
1.- For example, say you start with the words
["abcdef","abndef"]both initially abbreviated as"a4f". Then, a sequence of operations would be["a4f","a4f"]->["ab3f","ab3f"]->["abc2f","abn2f"].
- For example, say you start with the words
- This operation is repeated until every abbreviation is unique.
- Increase the prefix (characters in the first part) of each of their abbreviations by
- At the end, if an abbreviation did not make a word shorter, then keep it as the original word.
Example 1:
Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"] Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
Example 2:
Input: words = ["aa","aaa"] Output: ["aa","aaa"]
Constraints:
1 <= words.length <= 4002 <= words[i].length <= 400words[i]consists of lowercase English letters.- All the strings of
wordsare unique.
We notice that if two words have the same abbreviation, their first and last letters must be the same, and their lengths must be the same. Therefore, we can group all words by length and last letter, and use a trie to store the information of each group of words.
The structure of each node in the trie is as follows:
-
children: An array of length$26$ , representing all child nodes of this node. -
cnt: The number of words passing through this node.
For each word, we insert it into the trie and record the cnt value of each node.
When querying, we start from the root node. For the current letter, if the cnt value of its corresponding child node is
The time complexity is
class Trie:
__slots__ = ["children", "cnt"]
def __init__(self):
self.children = [None] * 26
self.cnt = 0
def insert(self, w: str):
node = self
for c in w:
idx = ord(c) - ord("a")
if not node.children[idx]:
node.children[idx] = Trie()
node = node.children[idx]
node.cnt += 1
def search(self, w: str) -> int:
node = self
cnt = 0
for c in w:
cnt += 1
idx = ord(c) - ord("a")
node = node.children[idx]
if node.cnt == 1:
return cnt
return len(w)
class Solution:
def wordsAbbreviation(self, words: List[str]) -> List[str]:
tries = {}
for w in words:
m = len(w)
if (m, w[-1]) not in tries:
tries[(m, w[-1])] = Trie()
tries[(m, w[-1])].insert(w)
ans = []
for w in words:
cnt = tries[(len(w), w[-1])].search(w)
ans.append(
w if cnt + 2 >= len(w) else w[:cnt] + str(len(w) - cnt - 1) + w[-1]
)
return ansclass Trie {
private final Trie[] children = new Trie[26];
private int cnt;
public void insert(String w) {
Trie node = this;
for (char c : w.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new Trie();
}
node = node.children[idx];
++node.cnt;
}
}
public int search(String w) {
Trie node = this;
int ans = 0;
for (char c : w.toCharArray()) {
++ans;
int idx = c - 'a';
node = node.children[idx];
if (node.cnt == 1) {
return ans;
}
}
return w.length();
}
}
class Solution {
public List<String> wordsAbbreviation(List<String> words) {
Map<List<Integer>, Trie> tries = new HashMap<>();
for (var w : words) {
var key = List.of(w.length(), w.charAt(w.length() - 1) - 'a');
tries.putIfAbsent(key, new Trie());
tries.get(key).insert(w);
}
List<String> ans = new ArrayList<>();
for (var w : words) {
int m = w.length();
var key = List.of(m, w.charAt(m - 1) - 'a');
int cnt = tries.get(key).search(w);
ans.add(cnt + 2 >= m ? w : w.substring(0, cnt) + (m - cnt - 1) + w.substring(m - 1));
}
return ans;
}
}class Trie {
public:
Trie()
: cnt(0) {
fill(children.begin(), children.end(), nullptr);
}
void insert(const string& w) {
Trie* node = this;
for (char c : w) {
int idx = c - 'a';
if (node->children[idx] == nullptr) {
node->children[idx] = new Trie();
}
node = node->children[idx];
++node->cnt;
}
}
int search(const string& w) {
Trie* node = this;
int ans = 0;
for (char c : w) {
++ans;
int idx = c - 'a';
node = node->children[idx];
if (node->cnt == 1) {
return ans;
}
}
return w.size();
}
private:
array<Trie*, 26> children;
int cnt;
};
class Solution {
public:
vector<string> wordsAbbreviation(vector<string>& words) {
map<pair<int, int>, Trie*> tries;
for (const auto& w : words) {
pair<int, int> key = {static_cast<int>(w.size()), w.back() - 'a'};
if (tries.find(key) == tries.end()) {
tries[key] = new Trie();
}
tries[key]->insert(w);
}
vector<string> ans;
for (const auto& w : words) {
int m = w.size();
pair<int, int> key = {m, w.back() - 'a'};
int cnt = tries[key]->search(w);
ans.push_back((cnt + 2 >= m) ? w : w.substr(0, cnt) + to_string(m - cnt - 1) + w.back());
}
return ans;
}
};type Trie struct {
children [26]*Trie
cnt int
}
func (t *Trie) insert(w string) {
node := t
for _, c := range w {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = &Trie{}
}
node = node.children[idx]
node.cnt++
}
}
func (t *Trie) search(w string) int {
node := t
ans := 0
for _, c := range w {
ans++
idx := c - 'a'
node = node.children[idx]
if node.cnt == 1 {
return ans
}
}
return len(w)
}
func wordsAbbreviation(words []string) (ans []string) {
tries := make(map[[2]int]*Trie)
for _, w := range words {
key := [2]int{len(w), int(w[len(w)-1] - 'a')}
_, exists := tries[key]
if !exists {
tries[key] = &Trie{}
}
tries[key].insert(w)
}
for _, w := range words {
m := len(w)
key := [2]int{m, int(w[m-1] - 'a')}
cnt := tries[key].search(w)
if cnt+2 >= m {
ans = append(ans, w)
} else {
abbr := w[:cnt] + fmt.Sprintf("%d", m-cnt-1) + w[m-1:]
ans = append(ans, abbr)
}
}
return
}class Trie {
private children: Trie[] = Array(26);
private cnt: number = 0;
insert(w: string): void {
let node: Trie = this;
for (const c of w) {
const idx: number = c.charCodeAt(0) - 'a'.charCodeAt(0);
if (!node.children[idx]) {
node.children[idx] = new Trie();
}
node = node.children[idx];
node.cnt++;
}
}
search(w: string): number {
let node: Trie = this;
let ans: number = 0;
for (const c of w) {
ans++;
const idx: number = c.charCodeAt(0) - 'a'.charCodeAt(0);
node = node.children[idx];
if (node.cnt === 1) {
return ans;
}
}
return w.length;
}
}
function wordsAbbreviation(words: string[]): string[] {
const tries: Map<string, Trie> = new Map();
for (const w of words) {
const key: string = `${w.length}-${w.charCodeAt(w.length - 1) - 'a'.charCodeAt(0)}`;
if (!tries.get(key)) {
tries.set(key, new Trie());
}
tries.get(key)!.insert(w);
}
const ans: string[] = [];
for (const w of words) {
const m: number = w.length;
const key: string = `${m}-${w.charCodeAt(m - 1) - 'a'.charCodeAt(0)}`;
const cnt: number = tries.get(key)!.search(w);
ans.push(cnt + 2 >= m ? w : w.substring(0, cnt) + (m - cnt - 1) + w.substring(m - 1));
}
return ans;
}