Day 3 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

*Problem: *
https://www.geeksforgeeks.org/problems/expression-add-operators/1

Expression Add Operators

Difficulty: Hard Accuracy: 61.49%
Given a string s that contains only digits (0-9) and an integer target, return all possible strings by inserting the binary operator ' + ', ' - ', and/or ' * ' between the digits of s such that the resultant expression evaluates to the target value.
Note:

1. Operands in the returned expressions should not contain leading zeros. For example, 2 + 03 is not allowed whereas 20 + 3 is fine.
2. It is allowed to not insert any of the operators.
3. Driver code will print the final list of strings in lexicographically smallest order. Examples: Input: s = "124", target = 9 Output: ["1+2*4"] Explanation: The valid expression that evaluate to 9 is 1 + 2 * 4 Input: s = "125", target = 7 Output: ["1*2+5", "12-5"] Explanation: The two valid expressions that evaluate to 7 are 1 * 2 + 5 and 12 - 5. Input: s = "12", target = 12 Output: ["12"] Explanation: s itself matches the target. No other expressions are possible. Input: s = "987612", target = 200 Output: [] Explanation: There are no expressions that can be created from "987612" to evaluate to 200. Constraints: 1 ≤ s.size() ≤ 9 s consists of only digits (0-9). -231 ≤ target ≤ 231-1

Solution:
class Solution:
def findExpr(self, s, target):
res = []
def backtrack(index, expr, value, last):
if index == len(s):
if value == target:
res.append(expr)
return
for i in range(index, len(s)):
if i != index and s[index] == '0':
break
num = int(s[index:i+1])
if index == 0:
backtrack(i+1, str(num), num, num)
else:
backtrack(i+1, expr + '+' + str(num), value + num, num)
backtrack(i+1, expr + '-' + str(num), value - num, -num)
backtrack(i+1, expr + '*' + str(num), value - last + last * num, last * num)
backtrack(0, '', 0, 0)
return sorted(res)