{x}
blog image

Apply Discount to Prices

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 <= 105
  • sentence consists of lowercase English letters, digits, ' ', and '$'.
  • sentence does not have leading or trailing spaces.
  • All words in sentence are separated by a single space.
  • All prices will be positive numbers without leading zeros.
  • All prices will have at most 10 digits.
  • 0 <= discount <= 100

Solution Explanation: Apply Discount to Prices

This problem requires processing a sentence, identifying words representing prices (e.g., "$10"), applying a discount, and formatting the discounted prices to two decimal places.

Approach:

The most efficient approach involves these steps:

  1. Split the Sentence: Divide the input sentence into individual words using space as a delimiter.

  2. Identify Prices: Iterate through each word. Check if a word starts with '$' and is followed only by digits. This indicates a price.

  3. Apply Discount: If a word is a price, convert the numeric part (after the '$') to a number, apply the discount calculation (price * (1 - discount/100)), and format the result to two decimal places using string formatting (e.g., %.2f in C/C++, :.2f in Python). Ensure the '$' is prepended.

  4. Reconstruct Sentence: Join the processed words (original words or discounted prices) back into a single string with spaces.

Code Implementation (Python):

class Solution:
    def discountPrices(self, sentence: str, discount: int) -> str:
        words = sentence.split()  # Split the sentence into words
        result = []
        for word in words:
            if word.startswith('$') and word[1:].isdigit():
                price = float(word[1:])
                discounted_price = price * (1 - discount / 100)
                result.append(f"${discounted_price:.2f}")  # Format to 2 decimal places
            else:
                result.append(word)
        return " ".join(result)

Time Complexity Analysis:

  • Splitting the sentence: O(n), where n is the length of the sentence. This is because splitting a string takes linear time.
  • Iterating through words: O(n) in the worst case (all words are prices).
  • Applying discount and formatting: O(1) for each word, as these are constant-time operations.

Therefore, the overall time complexity of the solution is O(n) – linear with respect to the length of the input sentence.

Space Complexity Analysis:

  • The space used by the words list is proportional to the number of words in the sentence, which is at most O(n) in the worst case (sentence with many short words).
  • The result list also uses space proportional to the number of words.

Hence, the space complexity is O(n). This is because we create new lists to store the words and the processed words. The space used is proportional to the input size. Note that the space used by the discounted price strings is a small constant factor and is not dominating.