527. Word Abbreviation¶

Approach 1: Brute Force¶

• Time: $O((\Sigma |\texttt{words[i]}|)^2)$
• Space: $O(\Sigma |\texttt{words[i]}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { public: vector wordsAbbreviation(vector& words) { const int n = words.size(); vector ans; // prefix[i] := ans[i] takes words[i][0..prefix[i]] vector prefix(n); for (const string& word : words) ans.push_back(getAbbrev(word, 0)); for (int i = 0; i < n; ++i) { while (true) { vector 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(); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public List wordsAbbreviation(List words) { final int n = words.size(); List 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) ans.add(getAbbrev(words.get(i), 0)); for (int i = 0; i < n; ++i) while (true) { List dupeIndices = new ArrayList<>(); for (int j = i + 1; j < n; ++j) if (ans.get(i).equals(ans.get(j))) dupeIndices.add(j); if (dupeIndices.isEmpty()) break; dupeIndices.add(i); 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); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 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 = [0] * 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]}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 struct IndexedWord { string word; int index; IndexedWord(const string& word, int index) : word(word), index(index) {} }; class Solution { public: vector wordsAbbreviation(vector& words) { const int n = words.size(); vector ans(n); unordered_map> 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) { ranges::sort(indexedWords, [](const auto& a, const auto& b) { return a.word < b.word; }); vector 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 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 wordsAbbreviation(List words) { String[] ans = new String[words.size()]; Map> abbrevToIndexedWords = new HashMap<>(); for (int i = 0; i < words.size(); ++i) { final String abbrev = getAbbrev(words.get(i), 0); abbrevToIndexedWords.putIfAbsent(abbrev, new ArrayList<>()); abbrevToIndexedWords.get(abbrev).add(new IndexedWord(words.get(i), i)); } for (List 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 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 = collections.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 = [0] * 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]}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 struct IndexedWord { string word; int index; IndexedWord(const string& word, int index) : word(word), index(index) {} }; struct TrieNode { vector> children; int count = 0; bool isWord = false; TrieNode() : children(26) {} }; class Solution { public: vector wordsAbbreviation(vector& words) { const int n = words.size(); vector ans(n); unordered_map> 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) { shared_ptr root = make_shared(); for (const IndexedWord& iw : indexedWords) insertWord(root, iw.word); for (const IndexedWord& 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(shared_ptr root, const string& word) { shared_ptr node = root; for (const char c : word) { const int i = c - 'a'; if (node->children[i] == nullptr) node->children[i] = make_shared(); node = node->children[i]; ++node->count; } } int firstUniqueIndex(shared_ptr root, const string& word) { shared_ptr 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(); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 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[26]; public int count = 0; } class Solution { public List wordsAbbreviation(List words) { String[] ans = new String[words.size()]; Map> abbrevToIndexedWords = new HashMap<>(); for (int i = 0; i < words.size(); ++i) { final String abbrev = getAbbrev(words.get(i), 0); abbrevToIndexedWords.putIfAbsent(abbrev, new ArrayList<>()); abbrevToIndexedWords.get(abbrev).add(new IndexedWord(words.get(i), i)); } for (List 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()) { final int i = c - 'a'; if (node.children[i] == null) node.children[i] = new TrieNode(); node = node.children[i]; ++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(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 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] = collections.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 = collections.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: node = node.children.setdefault(c, TrieNode()) 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