Apply Discount to Prices | Leetcode 2289 | Maps | Contest 295 🔥🔥
Apply Discount to Prices - Video Solution
Watch 6 video solutions for Apply Discount to Prices, a medium level problem involving String. This walkthrough by Coding Decoded has 1,783 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
A sentence is a string of single-space separated words where each word can contain digits, lowercase letters, and the dollar sign '$'. A word represents a price if it is a sequence of digits preceded by a dollar sign.
- For example,
"$100","$23", and"$6"represent prices while"100","$", and"$1e5"do not.
You are given a string sentence representing a sentence and an integer discount. For each word representing a price, apply a discount of discount% on the price and update the word in the sentence. All updated prices should be represented with exactly two decimal places.
Return a string representing the modified sentence.
Note that all prices will contain at most 10 digits.
Example 1:
Input: sentence = "there are $1 $2 and 5$ candies in the shop", discount = 50 Output: "there are $0.50 $1.00 and 5$ candies in the shop" Explanation: The words which represent prices are "$1" and "$2". - A 50% discount on "$1" yields "$0.50", so "$1" is replaced by "$0.50". - A 50% discount on "$2" yields "$1". Since we need to have exactly 2 decimal places after a price, we replace "$2" with "$1.00".
Example 2:
Input: sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100 Output: "1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$" Explanation: Applying a 100% discount on any price will result in 0. The words representing prices are "$3", "$5", "$6", and "$9". Each of them is replaced by "$0.00".
Constraints:
1 <= sentence.length <= 105sentenceconsists of lowercase English letters, digits,' ', and'$'.sentencedoes not have leading or trailing spaces.- All words in
sentenceare separated by a single space. - All prices will be positive numbers without leading zeros.
- All prices will have at most
10digits. 0 <= discount <= 100
Approach Overview
Problem Overview: You receive a sentence containing words separated by spaces. Some words represent prices that start with $ followed by digits. Apply a given percentage discount to those prices and return the updated sentence with each discounted value formatted to two decimal places.
Approach 1: Iterative Approach Using Split and Join (O(n) time, O(n) space)
Split the sentence into tokens using spaces. Iterate through each word and check whether it represents a valid price. A valid price starts with $ and the remaining characters are digits only. When a valid token is found, convert the numeric portion to a number, apply the discount using price * (100 - discount) / 100, and format the result to two decimal places. Replace the token with the discounted value and finally join all tokens back into a sentence. This approach relies on straightforward string processing and explicit validation logic.
The key insight is strict validation: tokens like $100 are valid, but $100a, $, or 100$ are not. Checking characters with digit validation ensures only legitimate price values are modified. Since each character in the sentence is processed once during splitting and validation, the time complexity is O(n), where n is the sentence length.
Approach 2: Regex and String Manipulation (O(n) time, O(n) space)
This approach uses a regular expression to detect valid price patterns directly. A pattern like \$[0-9]+ identifies words beginning with $ followed strictly by digits. After locating matches, extract the numeric portion, compute the discounted value, and replace the match with the formatted result.
Regex reduces manual validation logic and makes the pattern definition explicit. The algorithm scans the string once while applying replacements, which keeps the time complexity at O(n). This method is common when working with structured text and regular expressions. It pairs well with languages like C++ or Java that provide efficient regex utilities.
Recommended for interviews: The split-and-iterate approach is usually preferred in interviews. It shows you can validate tokens, manipulate string data, and control formatting without relying on heavy libraries. The regex solution is concise and practical for production code but may hide some of the logic interviewers want to see. Demonstrating the iterative validation first, then mentioning regex as an alternative, shows both algorithmic clarity and real-world engineering judgment.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Split and Join | O(n) | O(n) | Best for interviews and clear token validation logic |
| Regex and String Manipulation | O(n) | O(n) | When pattern matching tools are available and concise code is preferred |