Leetcode

Word Abbreviation

May 26, 2022 by aAshish

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)
      ans.add(getAbbrev(words.get(i), 0));

    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)))
            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);
  }
}

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 = [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]}|)

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<>());
      abbrevToIndexedWords.get(abbrev).add(new IndexedWord(words.get(i), i));
    }

    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 = [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]}|)

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[26];
  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<>());
      abbrevToIndexedWords.get(abbrev).add(new IndexedWord(words.get(i), i));
    }

    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