This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
241. Different Ways to Add Parentheses
Difficulty: Medium
Topics: Math, String, Dynamic Programming, Recursion, Memoization
Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.
The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 104.
Example 1:
- Input: expression = "2-1-1"
- Output: [0,2]
- Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2
Example 2:
- Input: expression = "2*3-4*5"
- Output: [-34,-14,-10,-10,10]
- Explanation:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Constraints:
1 <= expression.length <= 20-
expressionconsists of digits and the operator'+','-', and'*'. - All the integer values in the input expression are in the range
[0, 99]. - The integer values in the input expression do not have a leading
'-'or'+'denoting the sign.
Solution:
We can use recursion combined with memoization to store previously computed results for sub-expressions, as this avoids redundant calculations and optimizes the solution.
Approach:
-
Recursion:
- For each operator in the string (
+,-,*), we split the expression at that operator. - Recursively compute the left and right parts of the expression.
- Combine the results of both parts using the operator.
- For each operator in the string (
-
Memoization:
- Store the results of sub-expressions in an associative array to avoid recalculating the same sub-expression multiple times.
-
Base Case:
- If the expression contains only a number (i.e., no operators), return that number as the result.
Example Walkthrough:
For the input "2*3-4*5":
- Split at
*->2and3-4*5- Recursively compute
3-4*5and2, then combine.
- Recursively compute
- Split at
-->2*3and4*5- Recursively compute each and combine.
- Similarly for other splits.
Let's implement this solution in PHP: 241. Different Ways to Add Parentheses
<?php
class Solution {
/**
* @var array
*/
private $memo = [];
/**
* @param String $expression
* @return Integer[]
*/
public function diffWaysToCompute($expression) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* @param $expression
* @return array|mixed
*/
private function compute($expression) {
...
...
...
/**
* go to ./solution.php
*/
}
}
// Example usage
$solution = new Solution();
$expression1 = "2-1-1";
$expression2 = "2*3-4*5";
print_r($solution->diffWaysToCompute($expression1)); // Output: [0, 2]
print_r($solution->diffWaysToCompute($expression2)); // Output: [-34, -14, -10, -10, 10]
?>
Explanation:
-
Memoization: The
$memoarray stores the computed results for each expression to avoid redundant calculations. - Base Case: When the expression is numeric, it’s converted to an integer and added to the results.
- Recursive Splitting: For each operator in the expression, split it into left and right parts, recursively compute the results for both parts, and then combine them based on the operator.
-
Example Usage: The
diffWaysToComputefunction is tested with example expressions to verify the solution.
This approach ensures that you efficiently compute all possible results by leveraging memoization to avoid redundant computations.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
MD ARIFUL HAQUE | Sciencx (2024-09-19T18:16:28+00:00) 241. Different Ways to Add Parentheses. Retrieved from https://www.scien.cx/2024/09/19/241-different-ways-to-add-parentheses/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.