LeetCode 411: Minimum Unique Word Abbreviation Solution in Python – A Step-by-Step Guide

What Is LeetCode 411: Minimum Unique Word Abbreviation?

In LeetCode 411: Minimum Unique Word Abbreviation, you’re given a target string (e.g., "apple") and a list dictionary of strings (e.g., ["plain", "amber", "blade"]). Your task is to find the shortest abbreviation of target—using letters and numbers (e.g., "a2e" for "apple")—that doesn’t match any word in dictionary. Numbers represent skipped characters (e.g., "2" skips 2 letters), and the abbreviation must be valid (same length when expanded) and unique. For example, "apple" with ["blade"] can use "a4" (unique), but not "5" (matches "blade" length).

Problem Statement

• Input: A string target, a list of strings dictionary.
• Output: A string—the shortest unique abbreviation of target.
• Rules:
• Numbers in abbreviation count skipped characters.
• Abbreviation must expand to target length.
• Must not match any dictionary word’s abbreviation.

Constraints

• 1 <= target.length <= 20.
• 0 <= dictionary.length <= 100.
• 1 <= dictionary[i].length <= 20.
• All strings are lowercase letters.

Examples

• Input: target = "apple", dictionary = ["blade"]
• Output: "a4" (shortest unique abbreviation).
• Input: target = "apple", dictionary = ["blade","plain","amber"]
• Output: "a2e" (shortest unique).
• Input: target = "apple", dictionary = []
• Output: "5" (shortest possible).

Understanding the Problem: Crafting a Unique Shortcut

To solve LeetCode 411: Minimum Unique Word Abbreviation in Python, we need to find the shortest abbreviation of target that’s distinct from all dictionary words’ abbreviations. A naive idea might be to try every possible abbreviation—but with up to 20 characters, that’s 2²⁰ possibilities! Instead, we’ll use:

• Best Solution (Bitmask with Pruning): O(2^n * d) time (n = target length, d = dictionary length), O(d) space—fast with smart cuts.
• Alternative Solution (DFS with Backtracking): O(2^n * d) time, O(n) space—explores systematically.

Let’s dive into the bitmask solution with a clear, step-by-step explanation.

Best Solution: Bitmask with Pruning

Why This Is the Best Solution

The bitmask with pruning approach is the top pick because it’s efficient—O(2^n * d) time, O(d) space—and cleverly uses binary numbers to generate abbreviations while pruning invalid ones early. It tries all combinations of keeping or skipping characters, builds the abbreviation, and checks against the dictionary, stopping when it finds the shortest unique one. It’s like flipping switches to find the tiniest code that stands out!

How It Works

Think of target as a row of switches (keep or skip):

• Step 1: Filter Dictionary:
• Only keep words same length as target (others can’t match).
• Step 2: Generate Masks:
• Use bitmasks (0 to 2^n - 1) where 1 = keep letter, 0 = skip.
• E.g., "apple" (5 letters), mask 10010 = "a..le".
• Step 3: Build Abbreviation:
• Convert mask to string (e.g., 10010 → "a3e").
• Count consecutive 0s as numbers, keep 1s as letters.
• Step 4: Check Uniqueness:
• Compare with each dictionary word’s abbreviation under same mask.
• If unique, track shortest length.
• Step 5: Prune:
• Start with masks having fewer 1s (shorter abbreviations).
• Stop once a valid one is found (shorter is better).
• Step 6: Why This Works:
• Bitmasks cover all possible abbreviations.
• Early pruning saves time by favoring short options.
• It’s like testing every shortcut, starting with the briefest!

Step-by-Step Example

Example: target = "apple", dictionary = ["blade"]

• Filter: ["blade"] (same length 5).
• Masks (5 bits, try shortest first):
• Mask 00001 (1): "....e" → "4e".
• "blade" → "4e" (b...e), matches, skip.
• Mask 10000 (16): "a...." → "a4".
• "blade" → "b4" (b....), unique ✓.
• Length 2: "a4" works, stop (shortest unique).
• Result: "a4".

Example: target = "apple", dictionary = ["blade","plain"]

• Mask 10000: "a4".
• "blade" → "b4", "plain" → "p4", unique ✓.
• Result: "a4" (length 2, shortest).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:
        # Step 1: Filter dictionary by length
        n = len(target)
        valid_dict = [word for word in dictionary if len(word) == n]
        if not valid_dict:
            return str(n)  # Shortest if no conflicts

        # Step 2: Function to build abbreviation from mask
        def get_abbr(mask):
            abbr = ""
            skip = 0
            for i in range(n):
                if mask & (1 << i):  # Keep this letter
                    if skip > 0:
                        abbr += str(skip)
                        skip = 0
                    abbr += target[i]
                else:
                    skip += 1
            if skip > 0:
                abbr += str(skip)
            return abbr

        # Step 3: Try masks, prioritize shorter
        min_len = n + 1
        result = ""
        for mask in range(1 << n):
            abbr = get_abbr(mask)
            if len(abbr) >= min_len:  # Prune longer ones
                continue

            # Check if unique
            is_unique = True
            for word in valid_dict:
                dict_abbr = ""
                skip = 0
                for i in range(n):
                    if mask & (1 << i):
                        if skip > 0:
                            dict_abbr += str(skip)
                            skip = 0
                        dict_abbr += word[i]
                    else:
                        skip += 1
                if skip > 0:
                    dict_abbr += str(skip)
                if dict_abbr == abbr:
                    is_unique = False
                    break

            if is_unique:
                min_len = len(abbr)
                result = abbr

        return result

• Line 4-7: Filter dictionary, return n if empty (e.g., "5" for "apple").
• Line 10-21: get_abbr function:
• Line 13-19: Build abbr from mask (e.g., 10010 → "a3e").
• 1 → add letter, 0 → increment skip.
• Add skip count before letter or at end.
• Line 24-43: Try masks:
• Line 25-27: Get abbr, skip if too long (pruning).
• Line 30-41: Check uniqueness:
• Build each dict word’s abbr with same mask.
• If matches, not unique, break.
• Line 42-43: If unique, update shortest result.
• Time Complexity: O(2^n * d)—masks times dict checks.
• Space Complexity: O(d)—valid_dict storage.

This is like flipping switches to find the tiniest unique code!

Alternative Solution: DFS with Backtracking

Why an Alternative Approach?

The DFS with backtracking method explores all abbreviation possibilities recursively, building and checking step-by-step. It’s O(2^n * d) time and O(n) space—more intuitive but less optimized. It’s like trying every shortcut path until you hit the shortest unique one!

How It Works

Picture it as building the abbreviation:

• Step 1: Start at position 0, empty string.
• Step 2: At each position:
• Keep letter, move next.
• Skip k letters (1 to remaining), add number, recurse.
• Step 3: Check uniqueness, track shortest.

Step-by-Step Example

Example: target = "apple", dictionary = ["blade"]

• DFS:
• "a" → "a4" (unique ✓).
• "5" (matches "blade" → "5", skip).
• Result: "a4".

Code for DFS Approach

Copy codeclass Solution:
    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:
        n = len(target)
        valid_dict = [word for word in dictionary if len(word) == n]
        if not valid_dict:
            return str(n)

        self.result = None
        self.min_len = n + 1

        def is_unique(abbr):
            for word in valid_dict:
                pos_w, pos_a, skip = 0, 0, 0
                while pos_a < len(abbr):
                    if abbr[pos_a].isdigit():
                        skip = int(abbr[pos_a:])
                        pos_w += skip
                        break
                    elif pos_w >= n or word[pos_w] != abbr[pos_a]:
                        break
                    pos_w += 1
                    pos_a += 1
                if pos_w + skip == n and pos_a == len(abbr):
                    return False
            return True

        def dfs(pos, abbr):
            if len(abbr) >= self.min_len:
                return
            if pos == n:
                if is_unique(abbr):
                    self.min_len = len(abbr)
                    self.result = abbr
                return

            # Keep current letter
            dfs(pos + 1, abbr + target[pos])
            # Skip k letters
            for k in range(1, n - pos + 1):
                dfs(pos + k, abbr + str(k))

        dfs(0, "")
        return self.result

• Time Complexity: O(2^n * d)—exponential paths, dict checks.
• Space Complexity: O(n)—recursion stack.

It’s a step-by-step shortcut explorer!

Comparing the Two Solutions

• Bitmask with Pruning (Best):
• Pros: O(2^n * d), O(d), fast with pruning.
• Cons: Bitwise logic.
• DFS with Backtracking (Alternative):
• Pros: O(2^n * d), O(n), intuitive.
• Cons: No early pruning.

Bitmask wins for speed.

Additional Examples and Edge Cases

• "a", []: "1".
• "ab", ["ac"]: "a1".
• "apple", ["apple"]: "a4" (must differ).

Bitmask handles all.

Complexity Breakdown

• Bitmask: Time O(2^n * d), Space O(d).
• DFS: Time O(2^n * d), Space O(n).

Bitmask’s leaner.

Key Takeaways

• Bitmask: Flip to win!
• DFS: Explore it out!
• Abbreviations: Uniqueness rules.
• Python Tip: Bits are fun—see [Python Basics](/python/basics).

Final Thoughts: Shorten Smart

LeetCode 411: Minimum Unique Word Abbreviation in Python is a word-shortening quest. Bitmask with pruning zaps to the answer, while DFS explores every path. Want more string fun? Try LeetCode 408: Valid Word Abbreviation or LeetCode 527: Word Abbreviation. Ready to abbreviate? Head to Solve LeetCode 411 on LeetCode and craft that shortcut today!