282. Expression Add Operators
leetcode hard
#csharp#hard#leetcode#recursion#string
Task
Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target.
Учтите, что операнды в возвращаемых выражениях не должны содержать ведущих нулей.
Пример:
Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.
C# solution
matched/originalusing System;
using System.Collections.Generic;
using System.Text;
public class Solution {
public List<string> answer;
public string digits;
public long target;
public void Recurse(int index, long previousOperand, long currentOperand, long value, List<string> ops) {
if (index == digits.Length) {
if (value == target && currentOperand == 0) {
StringBuilder sb = new StringBuilder();
for (int i = 1; i < ops.Count; i++) {
sb.Append(ops[i]);
}
answer.Add(sb.ToString());
}
return;
}
currentOperand = currentOperand * 10 + (digits[index] - '0');
string currentValRep = currentOperand.ToString();
if (currentOperand > 0) {
Recurse(index + 1, previousOperand, currentOperand, value, ops);
}
ops.Add("+");
ops.Add(currentValRep);
Recurse(index + 1, currentOperand, 0, value + currentOperand, ops);
ops.RemoveAt(ops.Count - 1);
ops.RemoveAt(ops.Count - 1);
if (ops.Count > 0) {
ops.Add("-");
ops.Add(currentValRep);
Recurse(index + 1, -currentOperand, 0, value - currentOperand, ops);
ops.RemoveAt(ops.Count - 1);
ops.RemoveAt(ops.Count - 1);
ops.Add("*");
ops.Add(currentValRep);
Recurse(index + 1, currentOperand * previousOperand, 0, value - previousOperand + (currentOperand * previousOperand), ops);
ops.RemoveAt(ops.Count - 1);
ops.RemoveAt(ops.Count - 1);
}
}
public IList<string> AddOperators(string num, int target) {
if (num.Length == 0) {
return new List<string>();
}
this.target = target;
this.digits = num;
this.answer = new List<string>();
Recurse(0, 0, 0, 0, new List<string>());
return answer;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public List<string> answer;
public string digits;
public long target;
public void Recurse(int index, long previousOperand, long currentOperand, long value, List<string> ops) {
if (index == digits.size()) {
if (value == target && currentOperand == 0) {
StringBuilder sb = new StringBuilder();
for (int i = 1; i < ops.size(); i++) {
sb.Append(ops[i]);
}
answer.push_back(sb.ToString());
}
return;
}
currentOperand = currentOperand * 10 + (digits[index] - '0');
string currentValRep = currentOperand.ToString();
if (currentOperand > 0) {
Recurse(index + 1, previousOperand, currentOperand, value, ops);
}
ops.push_back("+");
ops.push_back(currentValRep);
Recurse(index + 1, currentOperand, 0, value + currentOperand, ops);
ops.RemoveAt(ops.size() - 1);
ops.RemoveAt(ops.size() - 1);
if (ops.size() > 0) {
ops.push_back("-");
ops.push_back(currentValRep);
Recurse(index + 1, -currentOperand, 0, value - currentOperand, ops);
ops.RemoveAt(ops.size() - 1);
ops.RemoveAt(ops.size() - 1);
ops.push_back("*");
ops.push_back(currentValRep);
Recurse(index + 1, currentOperand * previousOperand, 0, value - previousOperand + (currentOperand * previousOperand), ops);
ops.RemoveAt(ops.size() - 1);
ops.RemoveAt(ops.size() - 1);
}
}
public vector<string> AddOperators(string num, int target) {
if (num.size() == 0) {
return new List<string>();
}
this.target = target;
this.digits = num;
this.answer = new List<string>();
Recurse(0, 0, 0, 0, new List<string>());
return answer;
}
}Java solution
matched/originalclass Solution {
public ArrayList<String> answer;
public String digits;
public long target;
public void recurse(
int index, long previousOperand, long currentOperand, long value, ArrayList<String> ops) {
String nums = this.digits;
if (index == nums.length()) {
if (value == this.target && currentOperand == 0) {
StringBuilder sb = new StringBuilder();
ops.subList(1, ops.size()).forEach(v -> sb.append(v));
this.answer.add(sb.toString());
}
return;
}
currentOperand = currentOperand * 10 + Character.getNumericValue(nums.charAt(index));
String current_val_rep = Long.toString(currentOperand);
int length = nums.length();
if (currentOperand > 0) {
recurse(index + 1, previousOperand, currentOperand, value, ops);
}
ops.add("+");
ops.add(current_val_rep);
recurse(index + 1, currentOperand, 0, value + currentOperand, ops);
ops.remove(ops.size() - 1);
ops.remove(ops.size() - 1);
if (ops.size() > 0) {
ops.add("-");
ops.add(current_val_rep);
recurse(index + 1, -currentOperand, 0, value - currentOperand, ops);
ops.remove(ops.size() - 1);
ops.remove(ops.size() - 1);
ops.add("*");
ops.add(current_val_rep);
recurse(
index + 1,
currentOperand * previousOperand,
0,
value - previousOperand + (currentOperand * previousOperand),
ops);
ops.remove(ops.size() - 1);
ops.remove(ops.size() - 1);
}
}
public List<String> addOperators(String num, int target) {
if (num.length() == 0) {
return new ArrayList<String>();
}
this.target = target;
this.digits = num;
this.answer = new ArrayList<String>();
this.recurse(0, 0, 0, 0, new ArrayList<String>());
return this.answer;
}
}JavaScript solution
matched/originalclass Solution {
constructor() {
this.answer = [];
this.digits = "";
this.target = 0;
}
recurse(index, previousOperand, currentOperand, value, ops) {
if (index === this.digits.length) {
if (value === this.target && currentOperand === 0) {
this.answer.push(ops.join(''));
}
return;
}
currentOperand = currentOperand * 10 + parseInt(this.digits[index]);
const currentValRep = currentOperand.toString();
if (currentOperand > 0) {
this.recurse(index + 1, previousOperand, currentOperand, value, ops);
}
ops.push("+", currentValRep);
this.recurse(index + 1, currentOperand, 0, value + currentOperand, ops);
ops.pop();
ops.pop();
if (ops.length > 0) {
ops.push("-", currentValRep);
this.recurse(index + 1, -currentOperand, 0, value - currentOperand, ops);
ops.pop();
ops.pop();
ops.push("*", currentValRep);
this.recurse(index + 1, currentOperand * previousOperand, 0, value - previousOperand + (currentOperand * previousOperand), ops);
ops.pop();
ops.pop();
}
}
addOperators(num, target) {
if (num.length === 0) {
return [];
}
this.target = target;
this.digits = num;
this.answer = [];
this.recurse(0, 0, 0, 0, []);
return this.answer;
}
}Python solution
matched/originalclass Solution:
def __init__(self):
self.answer = []
self.digits = ""
self.target = 0
def recurse(self, index, previous_operand, current_operand, value, ops):
if index == len(self.digits):
if value == self.target and current_operand == 0:
self.answer.append("".join(ops[1:]))
return
current_operand = current_operand * 10 + int(self.digits[index])
str_operand = str(current_operand)
if current_operand > 0:
self.recurse(index + 1, previous_operand, current_operand, value, ops)
ops.append("+")
ops.append(str_operand)
self.recurse(index + 1, current_operand, 0, value + current_operand, ops)
ops.pop()
ops.pop()
if ops:
ops.append("-")
ops.append(str_operand)
self.recurse(index + 1, -current_operand, 0, value - current_operand, ops)
ops.pop()
ops.pop()
ops.append("*")
ops.append(str_operand)
self.recurse(index + 1, current_operand * previous_operand, 0, value - previous_operand + (current_operand * previous_operand), ops)
ops.pop()
ops.pop()
def addOperators(self, num, target):
if not num:
return []
self.target = target
self.digits = num
self.answer = []
self.recurse(0, 0, 0, 0, [])
return self.answerGo solution
matched/originalimport (
"strconv"
)
type Solution struct {
answer []string
digits string
target int64
}
func (s *Solution) recurse(index int, previousOperand, currentOperand, value int64, ops []string) {
if index == len(s.digits) {
if value == s.target && currentOperand == 0 {
expression := ""
for i := 1; i < len(ops); i++ {
expression += ops[i]
}
s.answer = append(s.answer, expression)
}
return
}
currentOperand = currentOperand*10 + int64(s.digits[index]-'0')
currentValRep := strconv.FormatInt(currentOperand, 10)
if currentOperand > 0 {
s.recurse(index+1, previousOperand, currentOperand, value, ops)
}
ops = append(ops, "+", currentValRep)
s.recurse(index+1, currentOperand, 0, value+currentOperand, ops)
ops = ops[:len(ops)-2]
if len(ops) > 0 {
ops = append(ops, "-", currentValRep)
s.recurse(index+1, -currentOperand, 0, value-currentOperand, ops)
ops = ops[:len(ops)-2]
ops = append(ops, "*", currentValRep)
s.recurse(index+1, currentOperand*previousOperand, 0, value-previousOperand+(currentOperand*previousOperand), ops)
ops = ops[:len(ops)-2]
}
}
func (s *Solution) addOperators(num string, target int) []string {
if len(num) == 0 {
return []string{}
}
s.target = int64(target)
s.digits = num
s.answer = []string{}
s.recurse(0, 0, 0, 0, []string{})
return s.answer
}Explanation
Algorithm
Инициализация и рекурсивный вызов:
Создайте класс Solution с полями для хранения результирующих выражений, строки цифр и целевого значения.
Инициализируйте эти поля в методе addOperators и запустите рекурсивный метод для генерации всех возможных выражений.
Рекурсивная генерация выражений:
В методе recurse на каждом шаге рассматривайте текущий индекс, предыдущий операнд, текущий операнд и текущее значение выражения.
Обрабатывайте все возможные операторы: без оператора (расширение текущего операнда), сложение, вычитание и умножение. На каждом шаге обновляйте текущее значение и выражение.
Проверка и запись валидных выражений:
Когда вся строка цифр обработана, проверяйте, соответствует ли итоговое значение целевому значению и нет ли остатков операндов.
Если выражение валидное, записывайте его в список результатов.
😎