Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/411.html

411. Minimum Unique Word Abbreviation

Level

Hard

Description

A string such as "word" contains the following abbreviations:

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Given a target string and a set of strings in a dictionary, find an abbreviation of this target string with the smallest possible length such that it does not conflict with abbreviations of the strings in the dictionary.

Each number or letter in the abbreviation is considered length = 1. For example, the abbreviation “a32bc” has length = 4.

Note:

• In the case of multiple answers as shown in the second example below, you may return any one of them.
• Assume length of target string = m, and dictionary size = n. You may assume that m ≤ 21, n ≤ 1000, and log₂(n) + m ≤ 20.

Examples:

"apple", ["blade"] -> "a4" (because "5" or "4e" conflicts with "blade")

"apple", ["plain", "amber", "blade"] -> "1p3" (other valid answers include "ap3", "a3e", "2p2", "3le", "3l1").

Solution

If the given target has length n, then since each character can either be in the abbreviation state or in the original state, there are 2ⁿ possible abbreviations in total.

Initialize the minimum abbreviation to target and the minimum abbreviation length to n. Then for each abbreviation, if it does not conflict with abbreviations of the strings in the dictionary and is shorter than the minimum abbreviation, then update the minimum abbreviation and the minimum abbreviation length.

To determine whether there is a conflict, loop over all words in the dictionary. For each word, if its length is the same as the target’s length, then check whether the current abbreviation of the word is the same as the target’s abbreviation. If so, there is a conflict. If no word has an abbreviation that is the same, then there is no conflict.

Finally, return the minimum abbreviation.

• Java
• Python

• class Solution {
      public String minAbbreviation(String target, String[] dictionary) {
          int length = target.length();
          int totalCount = 1 << length;
          String minAbbr = target;
          int minLength = length;
          for (int i = totalCount; i > 0; i--) {
              String abbr = generateAbbreviation(target, i);
              if (abbr.length() > minLength)
                  continue;
              boolean flag = true;
              for (String word : dictionary) {
                  if (word.length() == length) {
                      String abbr2 = generateAbbreviation(word, i);
                      if (abbr2.equals(abbr)) {
                          flag = false;
                          break;
                      }
                  }
              }
              if (flag) {
                  if (abbr.length() < minLength) {
                      minAbbr = abbr;
                      minLength = abbr.length();
                  }
              }
          }
          return minAbbr;
      }
  
      public String generateAbbreviation(String word, int num) {
          StringBuffer sb = new StringBuffer();
          int consecutiveCount = 0;
          int length = word.length();
          for (int i = 0; i < length; i++) {
              int cur = num & 1;
              if (cur == 1)
                  consecutiveCount++;
              else {
                  if (consecutiveCount > 0) {
                      sb.append(consecutiveCount);
                      consecutiveCount = 0;
                  }
                  sb.append(word.charAt(i));
              }
              num >>= 1;
          }
          if (consecutiveCount > 0)
              sb.append(consecutiveCount);
          return sb.toString();
      }
  }
  

• class Solution(object):
    def minAbbreviation(self, target, dictionary):
      """
      :type target: str
      :type dictionary: List[str]
      :rtype: str
      """
  
      def dfs(w, start, res):
        res.append(w)
        for i in range(start, len(w)):
          for l in reversed(range(1, len(w) - i + 1)):
            dfs(w[:i] + [str(l)] + w[i + l:], i + 2, res)
  
      def match(src, dest):
        i = 0
        for c in src:
          if c.isdigit():
            jump = int(c)
            i += jump
          else:
            if c != dest[i]:
              return False
            i += 1
        return True
  
      if not dictionary:
        return str(len(target))
      wordLen = len(target)
      res = []
      dfs(list(target), 0, res)
      res.sort(key=lambda x: len(x))
      dictionary = filter(lambda s: len(s) == wordLen, dictionary)
  
      for w in res:
        allMiss = True
        for d in dictionary:
          if match(w, d):
            allMiss = False
            break
        if allMiss:
          return "".join(w)
      return None
  
  

All Problems

All Solutions