Practice-Leetcode/NumberToExpression.cpp at master · adilhamid/Practice-Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include "import.h"

using namespace std;

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        unordered_map<string, int> dpMap;
        vector<string> result = computeWithDp(num, dpMap);

		for (string str : result) {
			if(dpMap[str] == target)
				cout << str << " = " << dpMap[str] << endl;
		}

		return {} ;
    }

    vector<string> computeWithDp(string input, unordered_map<string, int> &dpMap){

      vector<string> result;

	  int size = input.size();

	  if (size == 1) {
		  result.push_back(input);
		  return result;
	  }

      for(int i =1; i< size; i++){

        vector<string> result1, result2;

        string curr = input.substr(0,i);

		if (curr.length()>1) {
			result1 = computeWithDp(curr, dpMap);
		}
		else {
			dpMap[curr] = stoi(curr);
			result1.push_back(curr);
		}

        string substr = input.substr(i);

         if(substr.length()>1){
             result2 = computeWithDp(substr, dpMap);
         }
		 else {
			 dpMap[substr] = stoi(substr);
			 result2.push_back(substr);
		 }

		 for(string str1 : result1)
			 for (string str2 : result2) {

				 result.push_back("(" + str1 + "+" + str2 + ")");
				 dpMap["(" + str1 + "+" + str2 + ")"] = dpMap[str1] + dpMap[str2];

				 result.push_back("(" + str1 + "-" + str2 + ")");
				 dpMap["(" + str1 + "-" + str2 + ")"] = dpMap[str1] - dpMap[str2];

				 result.push_back("(" + str1 + "*" + str2 + ")");
				 dpMap["(" + str1 + "*" + str2 + ")"] = dpMap[str1] * dpMap[str2];

			 }
      }
        return result;
    }
};


int main() {
	Solution obj;

	obj.addOperators("232", 8);

	return 0;
}