Skip to content

411. Minimum Unique Word Abbreviation

  • Time: $O(2^m \cdot nm)$
  • Space: $O(2^m \cdot m)$
 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution {
 public:
  string minAbbreviation(string target, vector<string>& dictionary) {
    const int m = target.length();
    vector<int> masks;

    for (const string& word : dictionary) {
      if (word.length() != m)
        continue;
      masks.push_back(getMask(target, word));
    }

    if (masks.empty())
      return to_string(m);

    vector<string> abbrs;

    const int maxCand = pow(2, m);
    // all the candidate representation of the target
    for (int cand = 0; cand < maxCand; ++cand)
      // All the masks have at lease one bit different from the candidate.
      if (ranges::all_of(masks, [cand](int mask) { return cand & mask; }))
        abbrs.push_back(getAbbr(target, cand));

    string ans = target;

    for (const string& abbr : abbrs)
      if (getAbbrLen(abbr) < getAbbrLen(ans))
        ans = abbr;

    return ans;
  }

 private:
  int getMask(const string& target, const string& word) {
    const int m = target.length();
    // mask[i] = 0 := target[i] == word[i]
    // mask[i] = 1 := target[i] != word[i]
    // e.g. target = "apple"
    //        word = "blade"
    //        mask =  11110
    int mask = 0;
    for (int i = 0; i < m; ++i)
      if (word[i] != target[i])
        mask |= 1 << m - 1 - i;
    return mask;
  }

  string getAbbr(const string& target, int cand) {
    const int m = target.length();
    string abbr;
    int replacedCount = 0;
    for (int i = 0; i < m; ++i)
      if (cand >> m - 1 - i & 1) {
        // If cand[i] = 1, `abbr` should show the original character.
        if (replacedCount > 0)
          abbr += to_string(replacedCount);
        abbr += target[i];
        replacedCount = 0;
      } else {
        // If cand[i] = 0, `abbr` can be replaced.
        ++replacedCount;
      }
    if (replacedCount > 0)
      abbr += to_string(replacedCount);
    return abbr;
  }

  int getAbbrLen(const string& abbr) {
    int abbrLen = 0;
    int i = 0;
    int j = 0;
    while (i < abbr.length()) {
      if (isalpha(abbr[j]))
        ++j;
      else
        while (j < abbr.length() && isdigit(abbr[j]))
          ++j;
      ++abbrLen;
      i = j;
    }
    return abbrLen;
  }
};

 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution {
  public String minAbbreviation(String target, String[] dictionary) {
    final int m = target.length();
    List<Integer> masks = new ArrayList<>();

    for (final String word : dictionary) {
      if (word.length() != m)
        continue;
      masks.add(getMask(target, word));
    }

    if (masks.isEmpty())
      return String.valueOf(m);

    List<String> abbrs = new ArrayList<>();

    final int maxCand = (int) Math.pow(2, m);
    // all the candidate representation of the target
    for (int i = 0; i < maxCand; ++i) {
      final int cand = i;
      // All the masks have at lease one bit different from the candidate.
      if (masks.stream().allMatch(mask -> (cand & mask) > 0))
        abbrs.add(getAbbr(target, cand));
    }

    String ans = target;

    for (final String abbr : abbrs)
      if (getAbbrLen(abbr) < getAbbrLen(ans))
        ans = abbr;

    return ans;
  }

  private int getMask(final String target, final String word) {
    final int m = target.length();
    // mask[i] = 0 := target[i] == word[i]
    // mask[i] = 1 := target[i] != word[i]
    // e.g. target = "apple"
    //        word = "blade"
    //        mask =  11110
    int mask = 0;
    for (int i = 0; i < m; ++i)
      if (word.charAt(i) != target.charAt(i))
        mask |= 1 << m - 1 - i;
    return mask;
  }

  String getAbbr(final String target, int cand) {
    final int m = target.length();
    StringBuilder sb = new StringBuilder();
    int replacedCount = 0;
    for (int i = 0; i < m; ++i)
      if ((cand >> m - 1 - i & 1) == 1) {
        // If cand[i] = 1, `abbr` should show the original character.
        if (replacedCount > 0)
          sb.append(replacedCount);
        sb.append(target.charAt(i));
        replacedCount = 0;
      } else {
        // If cand[i] = 0, `abbr` can be replaced.
        ++replacedCount;
      }
    if (replacedCount > 0)
      sb.append(replacedCount);
    return sb.toString();
  }

  int getAbbrLen(final String abbr) {
    int abbrLen = 0;
    int i = 0;
    int j = 0;
    while (i < abbr.length()) {
      if (Character.isAlphabetic(abbr.charAt(j)))
        ++j;
      else
        while (j < abbr.length() && Character.isDigit(abbr.charAt(j)))
          ++j;
      ++abbrLen;
      i = j;
    }
    return abbrLen;
  }
}

 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
class Solution:
  def minAbbreviation(self, target: str, dictionary: list[str]) -> str:
    m = len(target)

    def getMask(word: str) -> int:
      # mask[i] = 0 := target[i] == word[i]
      # mask[i] = 1 := target[i] != word[i]
      # e.g. target = "apple"
      #        word = "blade"
      #        mask =  11110
      mask = 0
      for i, c in enumerate(word):
        if c != target[i]:
          mask |= 1 << m - 1 - i
      return mask

    masks = [getMask(word) for word in dictionary if len(word) == m]
    if not masks:
      return str(m)

    abbrs = []

    def getAbbr(cand: int) -> str:
      abbr = []
      replacedCount = 0
      for i, c in enumerate(target):
        if cand >> m - 1 - i & 1:
          # If cand[i] = 1, `abbr` should show the original character.
          if replacedCount:
            abbr += str(replacedCount)
          abbr.append(c)
          replacedCount = 0
        else:
          # If cand[i] = 0, `abbr` can be replaced.
          replacedCount += 1
      if replacedCount:
        abbr.append(str(replacedCount))
      return ''.join(abbr)

    # all the candidate representation of the target
    for cand in range(2**m):
      # All the masks have at lease one bit different from the candidate.
      if all(cand & mask for mask in masks):
        abbr = getAbbr(cand)
        abbrs.append(abbr)

    def getAbbrLen(abbr: str) -> int:
      abbrLen = 0
      i = 0
      j = 0
      while i < len(abbr):
        if abbr[j].isalpha():
          j += 1
        else:
          while j < len(abbr) and abbr[j].isdigit():
            j += 1
        abbrLen += 1
        i = j
      return abbrLen

    return min(abbrs, key=lambda x: getAbbrLen(x))