Ctrl K

Word Tape With Shared Endings

Medium
You need to write a list of words words onto a single tape so that every word can be read starting at some position on the tape and stopping right before the nearest #. The tape must end with a #. Short words do not always need an entry of their own: if a word is the ending of another word, it can be read from the middle of that one. For example, on the tape paint# the word int starts at position 2. Return the smallest possible length of the tape, counting every #.
Example 1
words=["stone", "one", "tone", "rope"] → 11

The tape stone#rope# has length 11: one and tone start inside stone and run to its #, while rope needs its own entry.

Example 2
words=["cat", "at", "bat"] → 8

at ends both cat and bat, but those two do not fit into each other: cat#bat#, length 8.

Example 3
words=["go", "go"] → 3

Repeated words can point to the same spot on the tape: go#, length 3.

Constraints
  • 1 ≤ len(words) ≤ 10⁴
  • 1 ≤ len(words[i]) ≤ 20
  • Words consist of lowercase English letters only
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsSplit Into Dictionary Words MediumHighlight Search Hits MediumShorten Words to Their Roots MediumMost Searched Words MediumWord Grown Letter by Letter Medium
loading Python…
Input
words=["stone", "one", "tone", "rope"]
Expected
11

Run checks the first 3 tests in your browser. Submit checks all 118 tests on the server, hidden ones included.