// intput string: "123"
// target = 6
// operators: + / -
// {{1+2+3}} // "1+(2+3)" NO
// "12-3" if target = 9
A:
// VM[0] {1-->"1"} // VM[1] {12->"12", 3->"1+2", -1-> "1-2" } // VM[2] { 123->'123" with itself // 24-> "1+23", -22->"1-23" , // combine 23 pre = VM[0] // 15-> "12+3" 9->"12-3" , 6-> "1+2+3" 0 -> "1+2-3" 4->"1-2+3" -5->"1-3-3"} // 3 comibine VM[1] vector<string> allPerm(string str, int target) { int n = str.length(); vector< unordered_map<int, vector<string>>> VM(n, unordered_map<int, vector<string>>()); if (str.length() == 0) { return vector<string>{}; } for (int i = 0; i < n; i++) { for (int start = 0; start <= i; start++) { string curStr = str.substr(start, i - start + 1); if (curStr.length() > 1 && curStr[0] == '0') // incase we have "00" as a candidate continue; int curVal = stoi(curStr); if (start == 0) { VM[i][curVal].push_back(curStr); } else { auto pre = VM[start - 1]; for (auto iter = pre.begin(); iter != pre.end(); iter++) { int preVal = iter->first; vector<string>& preStrs = iter->second; for (auto tmp : preStrs) { VM[i][preVal + curVal].push_back(tmp + "+" + curStr); VM[i][preVal - curVal].push_back(tmp + "-" + curStr); } } } } } return VM[n - 1][target]; }
No comments:
Post a Comment