How do you solve Apply Discount to Prices on LeetCode?

Apply Discount to Prices (LeetCode #2288) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Identifying valid prices requires checking the format of each word.

What is the brute force solution for Apply Discount to Prices?

The brute force approach for Apply Discount to Prices is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking each word in the sentence to see if it represents a price. If it does, we apply the discount and replace it in the sentence. This method is straightforward but inefficient for larger inputs. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Apply Discount to Prices?

Apply Discount to Prices uses the following concepts: String. The recommended patterns to study are: String Manipulation, Regular Expressions.

What are the interview tips for Apply Discount to Prices?

Always clarify the input format and constraints before starting. Think about edge cases, like no prices or all prices being discounted to zero. Practice string manipulation problems to get comfortable with them.

What are common mistakes when solving Apply Discount to Prices?

Not checking if the characters after '$' are digits. Forgetting to format the discounted price to two decimal places.

#2288

Apply Discount to Prices

Medium

StringString ManipulationRegular Expressions

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution leverages a single pass through the sentence to identify and update prices efficiently. This reduces the time complexity significantly while maintaining clarity in the code.

⚙️

Algorithm

6 steps

1Step 1: Split the sentence into words using space as a delimiter.
2Step 2: Initialize an empty list to store the modified words.
3Step 3: For each word, check if it starts with '$' and is followed by digits.
4Step 4: If it is a price, convert the price to a float, apply the discount, format it to two decimal places, and append it to the list.
5Step 5: If it is not a price, append the word unchanged.
6Step 6: Join the modified words back into a single string and return it.

solution.py15 lines

1# Full working Python code
2sentence = 'there are $1 $2 and 5$ candies in the shop'
3discount = 50
4
5words = sentence.split()
6modified_words = []
7for word in words:
8    if word.startswith('$') and word[1:].isdigit():
9        price = float(word[1:])
10        discounted_price = price * (1 - discount / 100)
11        modified_words.append(f'${discounted_price:.2f}')
12    else:
13        modified_words.append(word)
14result = ' '.join(modified_words)
15print(result)

ℹ

Complexity note: The time complexity is O(n) because we traverse the sentence once, processing each word in constant time. The space complexity is O(n) due to storing the modified words in a new list.

1Identifying valid prices requires checking the format of each word.
2Formatting numbers to two decimal places is crucial for price representation.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.