Minimum Unique Word Abbreviation — LeetCode 411 Python Solution
- Problem
- #411
- Pattern
- Backtracking
- Reading time
- 2 min
- Source
- leetcode.com
The problem
A string can be abbreviated by replacing any number of non-adjacent substrings with their lengths. For example, a string such as "substitution" could be abbreviated as (but not limited to): "s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("substitution") "su3i1u2on" ("su bst i t u ti on") "substitution" (no substrings replaced) Note that "s55n" ("s ubsti tutio n") is not a valid abbreviation of "substitution" because the replaced substrings are adjacent.
Example
- Input
- target = "apple", dictionary = ["blade"]
- Output
- "a4"
- Explanation
- The shortest abbreviation of "apple" is "5", but this is also an abbreviation of "blade".
Complexity
| Measure | Complexity |
|---|---|
| Time | Exponential (worst case) |
| Space | O(depth) auxiliary |
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 411. Minimum Unique Word Abbreviation is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 411. Minimum Unique Word Abbreviation?
- LeetCode 411. Minimum Unique Word Abbreviation is rated Hard on LeetCode.
- What topics does LeetCode 411. Minimum Unique Word Abbreviation cover?
- LeetCode 411. Minimum Unique Word Abbreviation is tagged Bit Manipulation, Array, String and Backtracking on LeetCode.
- Is LeetCode 411. Minimum Unique Word Abbreviation a premium problem?
- Yes. LeetCode 411. Minimum Unique Word Abbreviation is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.