Jobs

Interviews

Discussions

Expression Add Operators

Hard

4 views

Topics:

StringsRecursion

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Example 1:

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

Example 3:

Input: num = "3456237490", target = 9191
Output: []
Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191.

Constraints:

1 <= num.length <= 10
num consists of only digits.
-2³¹ <= target <= 2³¹ - 1

Expression Add Operators

Hard

4 views

Topics:

StringsRecursion

Note that operands in the returned expressions should not contain leading zeros.

Example 1:

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

Example 3:

Input: num = "3456237490", target = 9191
Output: []
Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191.

Constraints:

1 <= num.length <= 10
num consists of only digits.
-2³¹ <= target <= 2³¹ - 1

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `num` contain leading zeros? If so, how should I handle them when constructing numbers?
What is the range of values for the input integer `target` and the digits in the `num` string?
If no valid expressions can be formed, what should the function return? An empty list, null, or something else?
Are there any constraints on the length of the input string `num`? This will help me understand potential recursion depth.
Should the order of expressions in the returned list matter?

Brute Force Solution

Approach

The brute force approach to adding operators between digits tries every single possible combination of operators. We explore every way to insert '+', '-', or '*' between the digits in the input string and evaluate the resulting expression. We then check if the result equals the target value and save the valid expressions.

Here's how the algorithm would work step-by-step:

Start by considering the first digit as the beginning of an expression.
Then, try inserting a '+', '-', or '*' after the first digit and adding the second digit.
Continue this process, trying each possible operator after each digit and building up longer and longer expressions.
Each time you add a digit and an operator, calculate the result of the expression so far.
If you reach the end of the number string, check if the result of the complete expression equals the target value.
If the result equals the target, save the expression.
Repeat this process, trying every possible combination of operators until you've explored all possibilities.
Return all the saved expressions that resulted in the target value.

Code Implementation

def expression_add_operators_brute_force(number_string, target): 
    result_expressions = []

    def explore_expressions(index, current_expression, current_value, previous_operand):
        if index == len(number_string):
            # Base case: If we've processed all digits, check if the expression evaluates to the target.
            if current_value == target:
                result_expressions.append(current_expression)
            return

        for new_index in range(index + 1, len(number_string) + 1):
            substring = number_string[index:new_index]

            #Avoid leading zero
            if len(substring) > 1 and substring[0] == '0':
                continue

            current_operand = int(substring)

            if index == 0:
                explore_expressions(new_index, substring, current_operand, current_operand)
            else:
                #Try adding '+' operator
                explore_expressions(new_index, current_expression + '+' + substring, current_value + current_operand, current_operand)

                #Try adding '-' operator
                explore_expressions(new_index, current_expression + '-' + substring, current_value - current_operand, -current_operand)

                # Try adding '*' operator
                # Multiplication requires adjusting the previous result.
                explore_expressions(new_index, current_expression + '*' + substring, current_value - previous_operand + previous_operand * current_operand, previous_operand * current_operand)

    explore_expressions(0, "", 0, 0)
    return result_expressions

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(3^n) – The algorithm explores every possible combination of '+', '-', and '*' operators between the digits of the input string, which has a length of n. For each of the n-1 possible positions between the digits, there are 3 choices of operators. This leads to a branching factor of 3 at each of the n-1 positions. Therefore, the total number of possible expressions to evaluate is approximately 3^(n-1), which simplifies to O(3^n). The evaluation of each expression takes O(n) time in the worst case, but the dominant factor is the number of possible expressions.

Space Complexity

O(N) – The space complexity is dominated by the recursion depth. The algorithm explores inserting operators between each digit of the input string, leading to a maximum recursion depth proportional to the number of digits, N. Each recursive call creates a new stack frame to store intermediate results (like the current expression string and the current evaluated value), thus the maximum space used by the call stack will be proportional to N. This results in an auxiliary space of O(N).

Optimal Solution

Approach

The problem asks us to find all possible ways to insert +, -, and * operators into a string of digits so that the resulting expression evaluates to a target number. The clever part is to build expressions piece by piece, keeping track of the current result and the last number we added or subtracted, so we can handle the tricky multiplication correctly without recalculating everything from scratch.

Here's how the algorithm would work step-by-step:

Start by considering each digit or sequence of digits from the beginning of the string as the first operand in our expression.
For each such operand, try adding a +, -, or * operator after it, and then recursively call the same process on the remaining digits.
When we add or subtract, we simply update the current result by adding or subtracting the new operand.
Multiplication is trickier. We need to undo the previous addition or subtraction and then apply the multiplication. That's why we keep track of the last operand.
When we reach the end of the digit string, check if the current result matches the target value. If it does, we've found a valid expression.
Keep track of all the valid expressions we find along the way.
By building the expressions step-by-step and cleverly handling multiplication, we avoid recalculating the entire expression each time and efficiently explore the possible combinations.

Code Implementation

def expression_add_operators(numerical_string, target_value):
    results = []

    def add_operators_recursive(index, current_expression, current_result, previous_operand):
        if index == len(numerical_string):
            if current_result == target_value:
                results.append(current_expression)
            return

        for j in range(index + 1, len(numerical_string) + 1):
            current_substring = numerical_string[index:j]

            # Prevent leading zeros
            if len(current_substring) > 1 and current_substring[0] == '0':
                continue

            current_number = int(current_substring)

            if index == 0:
                add_operators_recursive(j, current_substring, current_number, current_number)
            else:
                add_operators_recursive(j, current_expression + "+" + current_substring, current_result + current_number, current_number)
                add_operators_recursive(j, current_expression + "-" + current_substring, current_result - current_number, current_number)

                # Multiplication requires special handling to revert the last operation.
                add_operators_recursive(j, current_expression + "*" + current_substring, current_result - previous_operand + previous_operand * current_number, previous_operand * current_number)

    add_operators_recursive(0, "", 0, 0)
    return results

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(4^n) – The dominant factor in the time complexity stems from the recursive exploration of possible expressions. At each digit, we have up to four choices: add +, -, *, or nothing (to form a multi-digit number). Since we have 'n' digits, in the worst case, we explore close to 4 options for each digit. This leads to a branching factor of approximately 4 at each of the 'n' digits, resulting in a time complexity of O(4^n). The arithmetic operations within each recursive call contribute a smaller, constant factor.

Space Complexity

O(N) – The space complexity is dominated by the recursion depth. In the worst-case scenario, where no operators are added (e.g., the entire input string forms a single number), the recursive calls can go as deep as the length of the input string, N, representing the number of digits. Each recursive call creates a new stack frame, storing local variables (like the current expression string, current result, and last operand). Thus, the auxiliary space used by the call stack is proportional to N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input string num	Return an empty list as there are no expressions possible.
Target is a very large or very small number causing potential integer overflow	Use long data type to store intermediate and final results to prevent overflow.
Leading zeros in the input string num (e.g., '05', '00')	Handle leading zeros to avoid invalid numbers such as '05' by skipping numbers with leading zeros or ensuring they are single '0'.
Very long input string num (performance concerns)	Consider memoization or other optimization techniques if the string length is extremely large.
Input string '0' and target 0	Should return '0' as a valid expression.
No possible expressions evaluate to the target	Return an empty list when no valid expressions are found.
Consecutive multiplication and addition/subtraction	Carefully track the last operand's value to correctly apply precedence rules for multiplication.
Single digit input num and target not matching	Return empty list if the single digit does not match the target value.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `num` contain leading zeros? If so, how should I handle them when constructing numbers?
What is the range of values for the input integer `target` and the digits in the `num` string?
If no valid expressions can be formed, what should the function return? An empty list, null, or something else?
Are there any constraints on the length of the input string `num`? This will help me understand potential recursion depth.
Should the order of expressions in the returned list matter?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the first digit as the beginning of an expression.
Then, try inserting a '+', '-', or '*' after the first digit and adding the second digit.
Continue this process, trying each possible operator after each digit and building up longer and longer expressions.
Each time you add a digit and an operator, calculate the result of the expression so far.
If you reach the end of the number string, check if the result of the complete expression equals the target value.
If the result equals the target, save the expression.
Repeat this process, trying every possible combination of operators until you've explored all possibilities.
Return all the saved expressions that resulted in the target value.

Code Implementation

def expression_add_operators_brute_force(number_string, target): 
    result_expressions = []

    def explore_expressions(index, current_expression, current_value, previous_operand):
        if index == len(number_string):
            # Base case: If we've processed all digits, check if the expression evaluates to the target.
            if current_value == target:
                result_expressions.append(current_expression)
            return

        for new_index in range(index + 1, len(number_string) + 1):
            substring = number_string[index:new_index]

            #Avoid leading zero
            if len(substring) > 1 and substring[0] == '0':
                continue

            current_operand = int(substring)

            if index == 0:
                explore_expressions(new_index, substring, current_operand, current_operand)
            else:
                #Try adding '+' operator
                explore_expressions(new_index, current_expression + '+' + substring, current_value + current_operand, current_operand)

                #Try adding '-' operator
                explore_expressions(new_index, current_expression + '-' + substring, current_value - current_operand, -current_operand)

                # Try adding '*' operator
                # Multiplication requires adjusting the previous result.
                explore_expressions(new_index, current_expression + '*' + substring, current_value - previous_operand + previous_operand * current_operand, previous_operand * current_operand)

    explore_expressions(0, "", 0, 0)
    return result_expressions

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering each digit or sequence of digits from the beginning of the string as the first operand in our expression.
For each such operand, try adding a +, -, or * operator after it, and then recursively call the same process on the remaining digits.
When we add or subtract, we simply update the current result by adding or subtracting the new operand.
Multiplication is trickier. We need to undo the previous addition or subtraction and then apply the multiplication. That's why we keep track of the last operand.
When we reach the end of the digit string, check if the current result matches the target value. If it does, we've found a valid expression.
Keep track of all the valid expressions we find along the way.
By building the expressions step-by-step and cleverly handling multiplication, we avoid recalculating the entire expression each time and efficiently explore the possible combinations.

Code Implementation

def expression_add_operators(numerical_string, target_value):
    results = []

    def add_operators_recursive(index, current_expression, current_result, previous_operand):
        if index == len(numerical_string):
            if current_result == target_value:
                results.append(current_expression)
            return

        for j in range(index + 1, len(numerical_string) + 1):
            current_substring = numerical_string[index:j]

            # Prevent leading zeros
            if len(current_substring) > 1 and current_substring[0] == '0':
                continue

            current_number = int(current_substring)

            if index == 0:
                add_operators_recursive(j, current_substring, current_number, current_number)
            else:
                add_operators_recursive(j, current_expression + "+" + current_substring, current_result + current_number, current_number)
                add_operators_recursive(j, current_expression + "-" + current_substring, current_result - current_number, current_number)

                # Multiplication requires special handling to revert the last operation.
                add_operators_recursive(j, current_expression + "*" + current_substring, current_result - previous_operand + previous_operand * current_number, previous_operand * current_number)

    add_operators_recursive(0, "", 0, 0)
    return results

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string num	Return an empty list as there are no expressions possible.
Target is a very large or very small number causing potential integer overflow	Use long data type to store intermediate and final results to prevent overflow.
Leading zeros in the input string num (e.g., '05', '00')	Handle leading zeros to avoid invalid numbers such as '05' by skipping numbers with leading zeros or ensuring they are single '0'.
Very long input string num (performance concerns)	Consider memoization or other optimization techniques if the string length is extremely large.
Input string '0' and target 0	Should return '0' as a valid expression.
No possible expressions evaluate to the target	Return an empty list when no valid expressions are found.
Consecutive multiplication and addition/subtraction	Carefully track the last operand's value to correctly apply precedence rules for multiplication.
Single digit input num and target not matching	Return empty list if the single digit does not match the target value.