You are viewing a single comment's thread. Return to all comments →
A C++ version:
int commonChild(const std::string &s1, const std::string &s2) { std::vector<int> vtable[2]; size_t s1_len = s1.length() + 1; size_t s2_len = s2.length() + 1; vtable[0].resize(s2_len, 0); vtable[1] = vtable[0]; for (auto i = 1; i < s1_len; ++i) { auto &prev = vtable[(i+1)%2]; auto &curr = vtable[i%2]; for (auto j = 1; j < s2_len; ++j) { if (s1[i-1] == s2[j-1]) { curr[j] = prev[j-1] + 1; } else { if (prev[j] > curr[j-1]) curr[j] = prev[j]; else curr[j] = curr[j-1]; } } } return vtable[(s1_len+1)%2][s2_len-1]; }
Seems like cookies are disabled on this browser, please enable them to open this website
Common Child
You are viewing a single comment's thread. Return to all comments →
A C++ version: