900. Compact Word Encoding
A warehouse prints its bin tags on one long label strip. Every tag in words must appear on the strip as a run of letters that is immediately followed by the marker #, and a tag may share its letters with a longer tag when it is a suffix of it: 'tle#' is already contained in 'kettle#'. Tags may repeat.
Return the length of the shortest possible strip, counting every letter and every #. Only tags that are not a suffix of another (different) tag need their own space; identical tags are stored once.
Aim for time linear in the total number of letters.
Example 1
- Input:
- words = ["kettle","tle","bottle","rivet"]
- Output:
- 20
- Explanation:
'tle' is a suffix of both 'kettle' and 'bottle', so only 'kettle#', 'bottle#' and 'rivet#' need storing: 7 + 7 + 6 = 20.
Example 2
- Input:
- words = ["pq","qq","q","pq"]
- Output:
- 6
- Explanation:
'q' ends 'pq' and 'qq' and the repeated 'pq' costs nothing extra, leaving 'pq#' and 'qq#': 3 + 3 = 6.
Example 3
- Input:
- words = ["moon","star","sun"]
- Output:
- 14
- Explanation:
No tag ends another tag, so the answer is 5 + 5 + 4 = 14.
Constraints
1 ≤ words.length ≤ 40000
1 ≤ words[i].length ≤ 10
Tags contain only lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(total letters)
- Space
- O(total letters)