LeetCode Solutions

			

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

			

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

			

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