2288. Apply Discount to Prices

MediumString
Leetcode Link

Problem Description

The problem presents us with a string called a sentence, which is comprised of several words separated by single spaces. Among these words, some are considered price words. A word is identified as a price if it starts with a dollar sign $ followed by a sequence of digits, such as $100 or $23. The task is to identify these price words and apply a given discount percentage to them. After applying the discount, the new price should be rounded to two decimal places, and the original price within the sentence should be updated to the new discounted price. The goal is to then return the modified sentence with the updated prices. The discount provided is an integer value, and prices in the sentence can have up to 10 digits.

Intuition

To solve this problem, we first need to identify the words that represent prices, which can be done by checking if a word starts with the $ sign and the following characters are all digits. For this, we iterate through each word in the sentence and apply this check.

Once we confirm a word is indeed a price, we proceed to calculate the discounted price. To do this, we strip the dollar sign and convert the remaining part of the string to an integer to get the original price. We then apply the discount by multiplying the original price by (1 - discount / 100) to obtain the discounted price.

To ensure that the discounted price is correctly formatted with two decimal places, we use Python's string formatting feature: "{:.2f}".format(discounted_price) or f'{discounted_price:.2f}'. The string formatting ensures the resulting price string will always have two decimal places.

After all the processing, we combine the words back into a single string making sure to add back the space separator between words, and return the modified sentence.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Solution Approach

To implement the solution to this problem, the solution makes use of some built-in Python features such as string methods and list comprehensions. Here's a step-by-step explanation of the approach:

  1. We start by splitting the given sentence into individual words. This is done with the .split() method, which, when used without any arguments, splits a string by white spaces.

  2. We iterate over each word in the list of words to determine if a word represents a price. This is identified by checking two conditions: the first character must be the dollar sign '$', and all the subsequent characters must be digits. This is checked using the str.isdigit() method on the slice of the word excluding the first character.

  3. For each word that represents a price, we remove the dollar sign and calculate the discounted price. This is achieved by converting the remaining string to an integer (int(w[1:])), then calculating the discount, which is the original price subtracted by the original price multiplied by the discount rate (int(w[1:]) * (1 - discount / 100)). The discount rate is created by dividing the discount by 100 since discount is given as a percentage.

  4. The discounted price is then formatted to have exactly two decimal places using Python's formatted string syntax: f'${discounted_price:.2f}'. This ensures that even if a discounted price is a whole number or has fewer than two decimal places, it will still be displayed with exactly two decimal places.

  5. The word list is then transformed by replacing the original price words with the new discounted price words where necessary.

  6. Finally, the words are joined back together into a single string sentence with white space separators using the .join() method. This reconstructed sentence, containing the updated prices, is returned as the final solution.

The code uses simple data structures like lists and strings and combines them with string formatting and list comprehension, which makes the approach efficient, as it requires only a single pass through the list of words. No complex data structures or algorithms are necessary due to the nature of the problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Example Walkthrough

Let's assume our input sentence is "I need $500 for groceries and $30 for the bus.", and the discount we are supposed to apply is 10%.

  1. We start by splitting the given sentence into individual words using the .split() method.

    Original sentence: "I need 500forgroceriesand500 for groceries and 30 for the bus." After splitting: ["I", "need", "$500", "for", "groceries", "and", "$30", "for", "the", "bus."]

  2. We iterate over each word in the list:

    • "I", "need", "for", "groceries", "and", "for", "the", "bus." do not start with $, so we keep them as they are.
    • "500"and"500" and "30" start with $ and are followed by digits, so they are identified as price words.

  3. For each price word:

    • We remove the dollar sign and convert the remaining part of the word to an integer: 500 and 30.
    • Apply the discount by multiplying the price by (1 - 0.10):
      • 500∗(1−0.10)=500 * (1 - 0.10) = 500 * 0.90 = $450.00
      • 30∗(1−0.10)=30 * (1 - 0.10) = 30 * 0.90 = $27.00

  4. The discounted prices are then formatted to have exactly two decimal places:

    • For 500witha10500 with a 10% discount: `f'{450.00:.2f}'results in"$450.00"`.
    • For 30witha1030 with a 10% discount: `f'{27.00:.2f}'results in"$27.00"`.

  5. We replace the original price words in the word list with the new discounted price words:

    Before: ["I", "need", "$500", "for", "groceries", "and", "$30", "for", "the", "bus."] After: ["I", "need", "$450.00", "for", "groceries", "and", "$27.00", "for", "the", "bus."]

  6. Finally, we join the words back together using the .join() method to form the final sentence:

    ["I", "need", "$450.00", "for", "groceries", "and", "$27.00", "for", "the", "bus."] becomes "I need 450.00forgroceriesand450.00 for groceries and 27.00 for the bus."

The method returns this modified sentence with updated prices, reflecting the applied discount.

Solution Implementation

1class Solution:
2    def discountPrices(self, sentence: str, discount: int) -> str:
3        # Initialize a list to hold the resulting words after processing
4        processed_words = []
5      
6        # Split the sentence into words
7        for word in sentence.split():
8            # Check if the word is a price (starts with '$' and followed by digits)
9            if word[0] == '$' and word[1:].isdigit():
10                # If it is a price, calculate the new price after the discount
11                original_price = int(word[1:])  # Remove the '$' sign and convert the rest to integer
12                discounted_price = original_price * (1 - discount / 100)  # Apply discount
13                word = f'${discounted_price:.2f}'  # Format the discounted price
14              
15            # Append the processed word to the list
16            processed_words.append(word)
17      
18        # Join the processed words back into a sentence and return it
19        return ' '.join(processed_words)
20
1class Solution {
2    /**
3     * Applies a discount to all prices within the sentence.
4     * 
5     * @param sentence The sentence containing potential prices.
6     * @param discount The discount rate to be applied.
7     * @return A sentence with discounts applied to valid prices.
8     */
9    public String discountPrices(String sentence, int discount) {
10        // Split the sentence into individual words
11        String[] words = sentence.split(" ");
12      
13        // Iterate over each word to check if it's a price
14        for (int i = 0; i < words.length; ++i) {
15            // If a word is a valid price, apply discount
16            if (isValidPrice(words[i])) {
17                // Parse the numeric value from the price, apply discount and convert it back to a string
18                double originalPrice = Long.parseLong(words[i].substring(1));
19                double discountedPrice = originalPrice * (1 - discount / 100.0);
20                words[i] = String.format("$%.2f", discountedPrice);
21            }
22        }
23      
24        // Join the words back into a single string with spaces between them
25        return String.join(" ", words);
26    }
27
28    /**
29     * Checks if a given string is a valid price format.
30     * 
31     * @param word The word to be checked.
32     * @return True if the word is a valid price; otherwise, False.
33     */
34    private boolean isValidPrice(String word) {
35        // A valid price must start with a dollar sign and have more than one character
36        if (word.charAt(0) != '$' || word.length() == 1) {
37            return false;
38        }
39      
40        // Check each character after the dollar sign to ensure they are digits
41        for (int i = 1; i < word.length(); ++i) {
42            if (!Character.isDigit(word.charAt(i))) {
43                return false;
44            }
45        }
46      
47        // If all checks pass, this is a valid price
48        return true;
49    }
50}
51
1#include <sstream> // For istringstream
2#include <string>
3#include <cctype> // For isdigit
4
5class Solution {
6public:
7    // Function to apply a discount to price tags in a given sentence
8    string discountPrices(string sentence, int discount) {
9        istringstream inputStream(sentence);
10        string word;
11        string answer;
12      
13        // Lambda function to check if a word is a valid price
14        auto isValidPrice = [](string s) {
15            // Price should start with '$' and be longer than 1 character
16            if (s[0] != '$' || s.size() == 1) {
17                return false;
18            }
19            // Check if all characters except the first are digits
20            for (int i = 1; i < s.size(); ++i) {
21                if (!isdigit(s[i])) {
22                    return false;
23                }
24            }
25            return true;
26        };
27
28        // Iterate over words in the input sentence
29        while (inputStream >> word) {
30            // If the word is a valid price, calculate the discounted price
31            if (isValidPrice(word)) {
32                // Extract numeric value , apply discount and convert back to price format
33                long long originalPrice = stoll(word.substr(1));
34                long long discountedPrice = originalPrice * (100 - discount);
35              
36                char formattedPrice[20];
37                // Format the discounted price to include dollars and cents
38                sprintf(formattedPrice, "$%lld.%02lld", discountedPrice / 100, discountedPrice % 100);
39                answer += formattedPrice;
40            } else {
41                // Keep the word unchanged if it's not a valid price
42                answer += word;
43            }
44            // Add a space after each word
45            answer += ' ';
46        }
47      
48        // Remove the trailing space from the last word
49        answer.pop_back();
50        return answer;
51    }
52};
53
1function discountPrices(sentence: string, discount: number): string {
2    // Calculate the multiplier for the discount (e.g., if discount is 20%, multiplier will be 0.8)
3    const discountMultiplier = (100 - discount) / 100;
4
5    // Regular expression to match prices in the format $[number] which may or may not have decimal places
6    // It ensures that the number doesn't start with 0 unless it's followed by a decimal point
7    let priceRegex = new RegExp(/^(\$)(([1-9]\d*\.?\d*)|(0\.\d*))$/g);
8
9    // Split the sentence into words, and map over each word to check for price patterns
10    let words = sentence.split(' ').map(word => {
11        // If word does not match the price format, return it unchanged
12        if (!priceRegex.test(word)) return word;
13
14        // If word is a price, apply the discount and format the result to two decimal places
15        return word.replace(priceRegex, (match, dollarSign, numericPart) => {
16            // Parse the numeric part as a float, apply the discount, and convert it back to a string
17            let discountedPrice = (parseFloat(numericPart) * discountMultiplier).toFixed(2);
18            return `${dollarSign}${discountedPrice}`; // Re-attach the dollar sign and return the discounted price
19        });
20    });
21
22    // Join the processed words back into a single string and return it
23    return words.join(' ');
24}
25
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Time and Space Complexity

Time Complexity

The given code has a primary loop that iterates over each word in the input sentence. This operation takes O(n) time where n is the number of characters in the input string since the split() function runs in O(n) time and iterations depend on the number of words which is proportional to the number of characters.

Inside the loop, the code checks whether a word starts with a dollar sign and then whether the rest of the word is a valid digit string. The check w[1:].isdigit() also takes at worst O(m) time where m is the number of characters in the word.

If a word is a valid price, it calculates the discounted price. The calculations inside the loop (int(w[1:]) * (1 - discount / 100)) run in constant time, O(1), however, formatting this to a string with two decimal places has a cost, but it is generally considered O(1).

Therefore, the total time complexity is O(n * m), however, if we consider that the length of the words can be bounded by a constant due to the nature of the prices (which doesn't usually exceed a certain number of digits), the complexity can also be represented as O(n) where n is the total number of characters in the sentence.

Space Complexity

The space complexity of the algorithm is due to the storage required for the list ans. This list stores each word after potentially modifying it. Since every word has to be stored regardless of whether it is modified, this means that it requires O(n) additional space, where n is the number of characters in the input string. The input string itself also takes O(n) space.

Thus, the space complexity of the code is O(n), where n represents the number of characters in the input string.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫