C++, with memoization, not using string manip

• This solution turns out to be a bit unwieldy, since vectors in C++ are more difficult to handle than strings.

``````class Solution {
public:
map<vector<int>, bool> memo = {};

static bool wayToSort(int i, int j) { return i > j; }

vector<int> vectorize(string s) {
vector<int> v {};
int runLength = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '+') {
runLength++;
}
if (i+1 == s.size() || s[i+1] == '-') {
if (runLength >= 2) v.push_back(runLength);
runLength = 0;
}
}
sort(v.begin(), v.end(), wayToSort);
return v;
}

bool canWinImpl(vector<int> v) {
if (v.empty()) return false;

auto s = memo.find(v);
if (s != memo.end()) { // We already have the answer in our memoization map
return s->second;
}

for (int j = 0; j < v.size(); j++) {
for (int subGameA = 0; subGameA < v[j] / 2; subGameA++) {
auto w = vector<int>(v); // Copy the original vector
w.erase(w.begin()+j); // Remove the original subgame
int subGameB = v[j] - subGameA - 2;
// If the remaining subgames are still valid, push them to the vector
if (subGameA >= 2) w.push_back(subGameA);
if (subGameB >= 2) w.push_back(subGameB);
sort(w.begin(), w.end(), wayToSort); // ensure that all equivalent memos are mapped to the same vector
if (!canWinImpl(w)) { // We made our move; if the opponent can't win, then we win
memo[v] = true;
return true;
}
}
}

// None of the available moves resulted in a win. We lose given this memo.
memo[v] = false;
return false;
}

bool canWin(string s) {
return canWinImpl(vectorize(s));
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.