Every Shorthand of a Word

Medium

A shorthand of a word is made by picking some non-overlapping runs of consecutive letters and replacing each run with a number, its length. Two picked runs cannot touch: at least one letter must remain between them (otherwise ab + cde would become an ambiguous 23). For example, the word house has the shorthands h3e, 1ous1, 5 and house itself. Given a word word, return all of its shorthands in any order.

Example 1

word="cat" → ['cat', 'ca1', 'c1t', 'c2', '1at', '1a1', '2t', '3']

Eight options: cat, ca1, c1t, c2, 1at, 1a1, 2t, 3. For example, c2 hides at, and 1a1 hides one letter at each end.

Example 2

word="z" → ['z', '1']

The letter is either kept or replaced with 1.

Constraints

1 ≤ len(word) ≤ 15
word consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation String Backtracking

Similar problems

Every Case Spelling Medium Two Disjoint Palindromic Picks Medium Binary Strings Without Two Zeros in a Row Medium Shortest Unambiguous Shorthand Hard Best Word Set From Tiles Hard

Input

word="cat"

Expected

['cat', 'ca1', 'c1t', 'c2', '1at', '1a1', '2t', '3']

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