You are viewing a single comment's thread. Return to all comments →
C++ with space optimization (more at https://github.com/IhorVodko/Hackerrank_solutions , feel free to give a star :) )usefull article https://en.wikipedia.org/wiki/Longest_common_subsequence
int commonChild( std::string const & _str1, std::string const & _str2 ){ assert(_str1.size() == _str2.size()); auto longestCommonSequence = std::vector<std::vector<size_t>>( 2, std::vector<size_t>(_str1.size() + 1, 0)); size_t row = 1; size_t col = 1; bool isLastRow = true; for(auto char1 = std::begin(_str1); char1 != std::end(_str1); ++char1 ){ row = isLastRow ? 1 : 0; col = 1; for(auto char2 = std::begin(_str2); char2 != std::end(_str2); ++char2 ){ if(*char1 == *char2){ longestCommonSequence.at(row).at(col) = longestCommonSequence.at( isLastRow ? row - 1 : row + 1).at(col - 1) + 1; }else{ longestCommonSequence.at(row).at(col) = std::max( longestCommonSequence.at( isLastRow ? row - 1 : row + 1).at(col), longestCommonSequence.at(row).at(col - 1)); } ++col; } isLastRow = !isLastRow; } return isLastRow ? longestCommonSequence.front().back() : longestCommonSequence.back().back(); }
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 →
C++ with space optimization (more at https://github.com/IhorVodko/Hackerrank_solutions , feel free to give a star :) )
usefull article https://en.wikipedia.org/wiki/Longest_common_subsequence