0462MediumStringEnumeration

Bracketing A Two-Run Price Ticket

Tracked in this browser only

Trains the technique from

LeetCode 2232Minimize Result by Adding Parentheses to Expression

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A market stall writes its prices as a ticket: a run of digits, a single '+', then another run of digits. Every digit is between '1' and '9', and both runs hold at least one digit.

The stallholder must add one '(' and one ')' to the ticket. The '(' goes immediately before one of the digits of the left run, and the ')' goes immediately after one of the digits of the right run, so the '+' always ends up inside the brackets. Nothing else about the ticket may change.

The bracketed ticket is then read like this: the bracketed part is the sum of the two digit runs inside it, and any digits left outside the brackets, on either side, multiply that sum. So 2(7+3)45 reads as 2 times 10 times 45. A side with no digits left outside contributes no multiplier at all.

Return the bracketed ticket, as a string, whose reading is the smallest possible. If several placements tie for the smallest reading, return the one whose '(' sits furthest left, and among those the one whose ')' sits furthest left.

Work the value out yourself: do not hand the ticket to a built-in expression evaluator.

Examples

Example 1

Input: ticket = "84+27"
Output: "(84+27)"

The whole ticket finishes up inside the brackets, so the reading is 84 plus 27, which is 111.

Example 2

Input: ticket = "7+652"
Output: "(7+65)2"

With the 2 left outside on the right, the ticket reads 72 times 2, which is 144.

Example 3

Input: ticket = "5391+8"
Output: "5(391+8)"

With the 5 left outside on the left, the ticket reads 5 times 399, which is 1995.

Constraints

3 <= ticket.length <= 10
ticket consists of the digits '1' to '9' and the character '+'.
ticket starts and ends with a digit.
ticket contains exactly one '+'.
The reading of the ticket, and of the ticket after any legal placement of the brackets, fits in a signed 32-bit integer.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def bracket_ticket(ticket: str) -> str:

Java

public String bracketTicket(String ticket)

The intended approach

Time O(L * R * n) for a left run of L digits and a right run of R digits, since each of the L * R placements parses O(n) characters.Space O(n) for the returned ticket and the slices taken while reading it.

The `'('` has one slot per digit of the left run and the `')'` one per digit of the right run, so there are only a few dozen tickets to weigh, and every one of them reads as four whole numbers taken off the ticket: the digits before the bracket, the two runs inside it, and the digits after it. Read those four off for each placement, treating an empty outside run as the multiplier 1 so it drops out, and keep the first placement that achieves the smallest reading, which is what the tie-break asks for.

Pythonentry point: bracket_ticket

def bracket_ticket(ticket):
    # There are only a few dozen legal placements, so weigh them all. The value
    # of a placement is fixed by four whole numbers read off the ticket, and an
    # absent multiplier simply drops out of the product.
    # O(L * R * n) time for runs of length L and R, O(n) extra space.
    plus = ticket.index("+")
    left = ticket[:plus]
    right = ticket[plus + 1:]
    best = None
    for i in range(len(left)):
        head = int(left[:i]) if i else 1
        first = int(left[i:])
        for j in range(1, len(right) + 1):
            second = int(right[:j])
            tail = int(right[j:]) if j < len(right) else 1
            worth = head * (first + second) * tail
            if best is None or worth < best[0]:
                best = (worth, i, j)
    _, i, j = best
    return left[:i] + "(" + left[i:] + "+" + right[:j] + ")" + right[j:]

The obvious version

Build the actual bracketed string for every legal placement, walk each one character by character to pull out the head, the two bracketed runs and the tail, and keep the smallest reading with placement positions breaking ties. O(L * R * n), the same order as the reference, so this is not asymptotically slower - it is an independent check that the ticket it returns really reads as claimed, not a slower baseline.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def _read_ticket(text):
    head = ""
    k = 0
    while text[k] != "(":
        head += text[k]
        k += 1
    k += 1
    first = ""
    while text[k] != "+":
        first += text[k]
        k += 1
    k += 1
    second = ""
    while text[k] != ")":
        second += text[k]
        k += 1
    k += 1
    tail = text[k:]
    worth = int(first) + int(second)
    if head:
        worth *= int(head)
    if tail:
        worth *= int(tail)
    return worth


def bf_bracket_ticket(ticket):
    plus = ticket.index("+")
    left = ticket[:plus]
    right = ticket[plus + 1:]
    best = None
    for i in range(len(left)):
        for j in range(1, len(right) + 1):
            shown = left[:i] + "(" + left[i:] + "+" + right[:j] + ")" + right[j:]
            key = (_read_ticket(shown), i, j)
            if best is None or key < best[0]:
                best = (key, shown)
    return best[1]

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in