# Pet Supply Store ## Solution 1: Left-to-Right Sequential Parsing ### Intuition - The string mixes numbers and letters, where numbers represent quantities and letters represent item types. - We read the string character by character, building up numbers as we encounter digits. - When we hit a valid unit letter, we multiply the accumulated quantity by that item's price. - If a number is not followed by a valid unit, it stands alone and gets added directly to the total. - A single pass through the string lets us handle all these cases cleanly. ### Approach - Scan the string from left to right, accumulating digits to form complete numbers. - When a valid unit character is found, multiply the accumulated number by the unit's price and add to total. - When an invalid character follows a number, add the number directly to the total and continue. - Handle the case where a unit appears without a preceding number by treating its quantity as 1. ### Pseudocode ``` function calculateTotalCost(S) { prices = {'f': 800, 't': 50, 'c': 200, 'b': 1200} total = 0 currentNum = 0 n = length of S for i = 0 to n - 1 { if S[i] is a digit { currentNum = currentNum * 10 + (S[i] - '0') } else if S[i] exists in prices { quantity = currentNum if quantity == 0 { quantity = 1 } total = total + quantity * prices[S[i]] currentNum = 0 } else { total = total + currentNum currentNum = 0 } } total = total + currentNum return total } ``` ### Code Implementation **C++** ```cpp #include using namespace std; class solution { public: int calculateTotalCost(string S) { unordered_map prices; prices['f'] = 800; prices['t'] = 50; prices['c'] = 200; prices['b'] = 1200; int total = 0; int currentNum = 0; int n = S.length(); for (int i = 0; i < n; i++) { if (isdigit(S[i])) { currentNum = currentNum * 10 + (S[i] - '0'); } else if (prices.find(S[i]) != prices.end()) { int quantity = currentNum > 0 ? currentNum : 1; total += quantity * prices[S[i]]; currentNum = 0; } else { total += currentNum; currentNum = 0; } } total += currentNum; return total; } }; ``` **Python** ```python class solution: def calculateTotalCost(self, S): prices = {'f': 800, 't': 50, 'c': 200, 'b': 1200} total = 0 currentNum = 0 for ch in S: if ch.isdigit(): currentNum = currentNum * 10 + int(ch) elif ch in prices: quantity = currentNum if currentNum > 0 else 1 total += quantity * prices[ch] currentNum = 0 else: total += currentNum currentNum = 0 total += currentNum return total ``` **Java** ```java import java.util.*; class Solution { public static int calculateTotalCost(String S) { HashMap prices = new HashMap<>(); prices.put('f', 800); prices.put('t', 50); prices.put('c', 200); prices.put('b', 1200); int total = 0; int currentNum = 0; int n = S.length(); for (int i = 0; i < n; i++) { char ch = S.charAt(i); if (Character.isDigit(ch)) { currentNum = currentNum * 10 + (ch - '0'); } else if (prices.containsKey(ch)) { int quantity = currentNum > 0 ? currentNum : 1; total += quantity * prices.get(ch); currentNum = 0; } else { total += currentNum; currentNum = 0; } } total += currentNum; return total; } } ``` **JavaScript** ```javascript class Solution { static calculateTotalCost(S) { const prices = {'f': 800, 't': 50, 'c': 200, 'b': 1200}; let total = 0; let currentNum = 0; for (let i = 0; i < S.length; i++) { const ch = S[i]; if (ch >= '0' && ch <= '9') { currentNum = currentNum * 10 + parseInt(ch); } else if (ch in prices) { const quantity = currentNum > 0 ? currentNum : 1; total += quantity * prices[ch]; currentNum = 0; } else { total += currentNum; currentNum = 0; } } total += currentNum; return total; } } ``` ### Complexity Analysis - **Time Complexity:** `O(n)` — single pass through the string. - **Space Complexity:** `O(1)` — fixed-size map and a few variables. --- ## Solution 2: Regular Expression Pattern Matching ### Intuition - The problem can be viewed as extracting all "quantity-unit" pairs and standalone numbers from the string. - Regular expressions provide a powerful way to match patterns like "number followed by unit" or "standalone number". - We can define patterns to capture all valid items, plain numbers, and handle them in batches. - This approach separates the parsing logic from the calculation logic, making the code more declarative. ### Approach - Use regex to find all patterns matching "one or more digits followed by a valid unit". - Multiply each captured number by its corresponding unit price and add to total. - Find all standalone numbers (not followed by a valid unit) and add them directly. - Find all units without preceding numbers and add their default price (quantity = 1). ### Pseudocode ``` function calculateTotalCost(S) { prices = {'f': 800, 't': 50, 'c': 200, 'b': 1200} total = 0 // Find all patterns: digit(s) followed by valid unit (e.g., "3f", "12b") pattern1 = one or more digits followed by f or t or c or b for each match in findAll(pattern1, S) { numPart = extract digits from match unitPart = extract unit character from match total = total + numPart * prices[unitPart] S = remove match from S } // Find all remaining valid units (without preceding number) for each unit in [f, t, c, b] { count = count occurrences of unit in S total = total + count * prices[unit] S = S with unit removed } // Find all remaining plain numbers in S pattern2 = one or more digits for each match in findAll(pattern2, S) { total = total + int(match) } return total } ``` ### Code Implementation **C++** ```cpp #include using namespace std; class solution { public: int calculateTotalCost(string S) { unordered_map prices; prices['f'] = 800; prices['t'] = 50; prices['c'] = 200; prices['b'] = 1200; int total = 0; string remaining = S; regex pattern("(\\d+)([ftcb])"); smatch match; while (regex_search(remaining, match, pattern)) { int quantity = stoi(match[1].str()); char unit = match[2].str()[0]; total += quantity * prices[unit]; remaining = match.prefix().str() + match.suffix().str(); } for (auto& pair : prices) { char unit = pair.first; int price = pair.second; int count = 0; for (char ch : remaining) { if (ch == unit) count++; } total += count * price; remaining.erase(remove(remaining.begin(), remaining.end(), unit), remaining.end()); } regex numPattern("(\\d+)"); while (regex_search(remaining, match, numPattern)) { total += stoi(match[1].str()); remaining = match.prefix().str() + match.suffix().str(); } return total; } }; ``` **Python** ```python import re class solution: def calculateTotalCost(self, S): prices = {'f': 800, 't': 50, 'c': 200, 'b': 1200} total = 0 pattern = r'(\d+)([ftcb])' matches = re.findall(pattern, S) for num, unit in matches: total += int(num) * prices[unit] remaining = re.sub(pattern, '', S) for unit, price in prices.items(): count = remaining.count(unit) total += count * price for unit in prices: remaining = remaining.replace(unit, '') num_pattern = r'\d+' plain_numbers = re.findall(num_pattern, remaining) for num in plain_numbers: total += int(num) return total ``` **Java** ```java import java.util.*; import java.util.regex.*; class Solution { public static int calculateTotalCost(String S) { HashMap prices = new HashMap<>(); prices.put('f', 800); prices.put('t', 50); prices.put('c', 200); prices.put('b', 1200); int total = 0; Pattern pattern = Pattern.compile("(\\d+)([ftcb])"); Matcher matcher = pattern.matcher(S); StringBuffer sb = new StringBuffer(); while (matcher.find()) { int quantity = Integer.parseInt(matcher.group(1)); char unit = matcher.group(2).charAt(0); total += quantity * prices.get(unit); matcher.appendReplacement(sb, ""); } matcher.appendTail(sb); String remaining = sb.toString(); for (Map.Entry entry : prices.entrySet()) { char unit = entry.getKey(); int price = entry.getValue(); int count = 0; for (char ch : remaining.toCharArray()) { if (ch == unit) count++; } total += count * price; } for (char unit : prices.keySet()) { remaining = remaining.replace(String.valueOf(unit), ""); } Pattern numPattern = Pattern.compile("\\d+"); Matcher numMatcher = numPattern.matcher(remaining); while (numMatcher.find()) { total += Integer.parseInt(numMatcher.group()); } return total; } } ``` **JavaScript** ```javascript class Solution { static calculateTotalCost(S) { const prices = {'f': 800, 't': 50, 'c': 200, 'b': 1200}; let total = 0; let remaining = S; const pattern = /(\d+)([ftcb])/g; let match; while ((match = pattern.exec(S)) !== null) { const quantity = parseInt(match[1]); const unit = match[2]; total += quantity * prices[unit]; } remaining = S.replace(/(\d+)([ftcb])/g, ''); for (const [unit, price] of Object.entries(prices)) { let count = 0; for (const ch of remaining) { if (ch === unit) count++; } total += count * price; } for (const unit of Object.keys(prices)) { remaining = remaining.split(unit).join(''); } const numPattern = /\d+/g; let numMatch; while ((numMatch = numPattern.exec(remaining)) !== null) { total += parseInt(numMatch[0]); } return total; } } ``` ### Complexity Analysis - **Time Complexity:** `O(n)` — regex operations scan the string a constant number of times. - **Space Complexity:** `O(n)` — intermediate string copies may be created during regex substitution.