1/**
2 * Trie (Prefix Tree) data structure to store words and count occurrences at each node
3 */
4class Trie {
5    // Array to store child nodes for each letter (a-z)
6    private final Trie[] children = new Trie[26];
7    // Counter to track how many words pass through this node
8    private int count;
9
10    /**
11     * Inserts a word into the trie and increments counters along the path
12     * @param word The word to insert into the trie
13     */
14    public void insert(String word) {
15        Trie currentNode = this;
16      
17        // Traverse each character in the word
18        for (char character : word.toCharArray()) {
19            int index = character - 'a';
20          
21            // Create new node if it doesn't exist
22            if (currentNode.children[index] == null) {
23                currentNode.children[index] = new Trie();
24            }
25          
26            // Move to child node and increment its counter
27            currentNode = currentNode.children[index];
28            currentNode.count++;
29        }
30    }
31
32    /**
33     * Searches for the minimum prefix length needed to uniquely identify the word
34     * @param word The word to search for
35     * @return The minimum number of characters needed as prefix
36     */
37    public int search(String word) {
38        Trie currentNode = this;
39        int prefixLength = 0;
40      
41        // Traverse each character in the word
42        for (char character : word.toCharArray()) {
43            prefixLength++;
44            int index = character - 'a';
45            currentNode = currentNode.children[index];
46          
47            // If only one word passes through this node, we found unique prefix
48            if (currentNode.count == 1) {
49                return prefixLength;
50            }
51        }
52      
53        // If no unique prefix found, return full word length
54        return word.length();
55    }
56}
57
58/**
59 * Solution class to generate word abbreviations
60 */
61class Solution {
62    /**
63     * Generates abbreviations for a list of words
64     * Words with same length and last character are grouped together
65     * @param words List of words to abbreviate
66     * @return List of abbreviated words
67     */
68    public List<String> wordsAbbreviation(List<String> words) {
69        // Map to group words by their length and last character
70        // Key: [word length, last character index], Value: Trie for that group
71        Map<List<Integer>, Trie> trieMap = new HashMap<>();
72      
73        // Build tries for each group of words
74        for (String word : words) {
75            // Create key based on word length and last character
76            List<Integer> groupKey = List.of(word.length(), word.charAt(word.length() - 1) - 'a');
77          
78            // Create new trie for this group if it doesn't exist
79            trieMap.putIfAbsent(groupKey, new Trie());
80          
81            // Insert word into the appropriate trie
82            trieMap.get(groupKey).insert(word);
83        }
84      
85        // Generate abbreviations for each word
86        List<String> result = new ArrayList<>();
87      
88        for (String word : words) {
89            int wordLength = word.length();
90          
91            // Get the trie for this word's group
92            List<Integer> groupKey = List.of(wordLength, word.charAt(wordLength - 1) - 'a');
93          
94            // Find minimum prefix length needed for unique identification
95            int prefixLength = trieMap.get(groupKey).search(word);
96          
97            // Check if abbreviation would be shorter than original word
98            // Abbreviation format: prefix + number + last character (minimum 3 chars)
99            if (prefixLength + 2 >= wordLength) {
100                // Abbreviation wouldn't save space, use original word
101                result.add(word);
102            } else {
103                // Create abbreviation: prefix + count of omitted chars + last char
104                String abbreviation = word.substring(0, prefixLength) + 
105                                     (wordLength - prefixLength - 1) + 
106                                     word.substring(wordLength - 1);
107                result.add(abbreviation);
108            }
109        }
110      
111        return result;
112    }
113}
114

1class Trie {
2public:
3    // Constructor initializes the trie node
4    Trie() : prefixCount(0) {
5        fill(children.begin(), children.end(), nullptr);
6    }
7
8    // Insert a word into the trie and update prefix counts
9    void insert(const string& word) {
10        Trie* currentNode = this;
11      
12        for (char ch : word) {
13            int index = ch - 'a';
14          
15            // Create new node if path doesn't exist
16            if (currentNode->children[index] == nullptr) {
17                currentNode->children[index] = new Trie();
18            }
19          
20            // Move to child node and increment its prefix count
21            currentNode = currentNode->children[index];
22            ++currentNode->prefixCount;
23        }
24    }
25
26    // Search for minimum unique prefix length for the given word
27    int search(const string& word) {
28        Trie* currentNode = this;
29        int prefixLength = 0;
30      
31        for (char ch : word) {
32            ++prefixLength;
33            int index = ch - 'a';
34            currentNode = currentNode->children[index];
35          
36            // If only one word has this prefix, we found the minimum unique prefix
37            if (currentNode->prefixCount == 1) {
38                return prefixLength;
39            }
40        }
41      
42        // If no unique prefix found, return full word length
43        return word.size();
44    }
45
46private:
47    array<Trie*, 26> children;  // Pointers to child nodes (26 letters)
48    int prefixCount;             // Number of words sharing this prefix
49};
50
51class Solution {
52public:
53    vector<string> wordsAbbreviation(vector<string>& words) {
54        // Map to group words by (length, last character)
55        // This ensures abbreviations are only compared among words with same length and ending
56        map<pair<int, int>, Trie*> trieGroups;
57      
58        // Build tries for each group of words
59        for (const auto& word : words) {
60            // Create key based on word length and last character
61            pair<int, int> groupKey = {
62                static_cast<int>(word.size()), 
63                word.back() - 'a'
64            };
65          
66            // Create new trie for this group if it doesn't exist
67            if (trieGroups.find(groupKey) == trieGroups.end()) {
68                trieGroups[groupKey] = new Trie();
69            }
70          
71            // Insert word into corresponding trie
72            trieGroups[groupKey]->insert(word);
73        }
74
75        vector<string> result;
76      
77        // Generate abbreviation for each word
78        for (const auto& word : words) {
79            int wordLength = word.size();
80          
81            // Find the trie group for this word
82            pair<int, int> groupKey = {wordLength, word.back() - 'a'};
83          
84            // Find minimum unique prefix length
85            int uniquePrefixLength = trieGroups[groupKey]->search(word);
86          
87            // Check if abbreviation would be shorter than original word
88            // Abbreviation format: prefix + number + last char (at least 3 chars)
89            if (uniquePrefixLength + 2 >= wordLength) {
90                // Abbreviation wouldn't save space, use original word
91                result.push_back(word);
92            } else {
93                // Create abbreviation: prefix + count of middle chars + last char
94                string abbreviation = word.substr(0, uniquePrefixLength) + 
95                                    to_string(wordLength - uniquePrefixLength - 1) + 
96                                    word.back();
97                result.push_back(abbreviation);
98            }
99        }
100
101        return result;
102    }
103};
104

1// Trie node structure for prefix tree
2interface TrieNode {
3    children: (TrieNode | null)[];  // Array of 26 child nodes (for 'a' to 'z')
4    count: number;                   // Number of words passing through this node
5}
6
7// Create a new Trie node
8function createTrieNode(): TrieNode {
9    return {
10        children: Array(26).fill(null),
11        count: 0
12    };
13}
14
15// Insert a word into the Trie and increment count for each node
16function insertIntoTrie(root: TrieNode, word: string): void {
17    let currentNode = root;
18  
19    for (const char of word) {
20        // Calculate index (0-25) for the character
21        const charIndex = char.charCodeAt(0) - 'a'.charCodeAt(0);
22      
23        // Create child node if it doesn't exist
24        if (!currentNode.children[charIndex]) {
25            currentNode.children[charIndex] = createTrieNode();
26        }
27      
28        // Move to child node and increment its count
29        currentNode = currentNode.children[charIndex]!;
30        currentNode.count++;
31    }
32}
33
34// Search for the minimum prefix length needed to uniquely identify the word
35function searchPrefixLength(root: TrieNode, word: string): number {
36    let currentNode = root;
37    let prefixLength = 0;
38  
39    for (const char of word) {
40        prefixLength++;
41      
42        // Calculate index for the character
43        const charIndex = char.charCodeAt(0) - 'a'.charCodeAt(0);
44        currentNode = currentNode.children[charIndex]!;
45      
46        // If only one word passes through this node, we found unique prefix
47        if (currentNode.count === 1) {
48            return prefixLength;
49        }
50    }
51  
52    // Return full word length if no unique prefix found
53    return word.length;
54}
55
56// Generate abbreviations for a list of words
57function wordsAbbreviation(words: string[]): string[] {
58    // Map to store Tries grouped by word length and last character
59    const trieMap: Map<string, TrieNode> = new Map();
60  
61    // Build Tries for each group of words with same length and last character
62    for (const word of words) {
63        // Create key using word length and last character
64        const wordLength = word.length;
65        const lastCharIndex = word.charCodeAt(wordLength - 1) - 'a'.charCodeAt(0);
66        const key = `${wordLength}-${lastCharIndex}`;
67      
68        // Create new Trie if key doesn't exist
69        if (!trieMap.has(key)) {
70            trieMap.set(key, createTrieNode());
71        }
72      
73        // Insert word into corresponding Trie
74        insertIntoTrie(trieMap.get(key)!, word);
75    }
76  
77    // Generate abbreviations for each word
78    const result: string[] = [];
79  
80    for (const word of words) {
81        const wordLength = word.length;
82      
83        // Create key to find corresponding Trie
84        const lastCharIndex = word.charCodeAt(wordLength - 1) - 'a'.charCodeAt(0);
85        const key = `${wordLength}-${lastCharIndex}`;
86      
87        // Find minimum prefix length for unique identification
88        const prefixLength = searchPrefixLength(trieMap.get(key)!, word);
89      
90        // Check if abbreviation would be shorter than original word
91        // Abbreviation format: prefix + number + last character (minimum 3 characters)
92        if (prefixLength + 2 >= wordLength) {
93            // Keep original word if abbreviation wouldn't save space
94            result.push(word);
95        } else {
96            // Create abbreviation: prefix + count of omitted characters + last character
97            const prefix = word.substring(0, prefixLength);
98            const omittedCount = wordLength - prefixLength - 1;
99            const lastChar = word.substring(wordLength - 1);
100            result.push(prefix + omittedCount + lastChar);
101        }
102    }
103  
104    return result;
105}
106