We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Abbreviation
Abbreviation
+ 0 comments A detailed look at the dynammic programming table approach with visual examples (but without code spoilers): https://github.com/KonstantinSimeonov/toptal-prep/blob/master/abbreviation.md
+ 0 comments Here is problem solution - https://programs.programmingoneonone.com/2021/03/hackerrank-abbreviation-solution.html
+ 1 comment In Sample Test 2, the second test case: case: beFgH EFG Expected Output: NO
How does it happen?
+ 0 comments here is a solution with time complexity
O(|b|*k)
, wherek = |a|-|b|+1
. So when both strings have length close to equal, the run time is close toO(N)
. Pass all test cases./* given a[0..i] matches to b[0..j], what if a[0..i+1] to b[0..j+1]? define dp[i][j] is either true of false, meaning the matching result between a[0..i] to b[0..j]. then dp[i][j] = dp[i-1][j-1] and toupper(a[i]) == b[j] or dp[i-1][j] and islower(a[i]) note that dp[i][j] = false for all i<j. the final answer is dp[A-1][B-1], where |a|=A and |b|=B so for any dp[i][j], i-j > (A-1)-(B-1) or i > j+A-B are not necessary now we can update dp as follow for j=[0...B) for i=[j...j+A-B] update dp[i][j] initially dp[-1][-1] = true dp[i][-1] = dp[i-1][j] and islower(a[i]) */ string abbreviation(string a, string b) { const int A = a.size(); const int B = b.size(); if (A < B) return "NO"; // size of dp array const int K = A-B+1; constexpr int COLS = 2; vector<vector<bool>> dp(K, vector<bool>(COLS, false)); cout << "begin init dp ... (-1+K)%K=" << ((-1+K)%K) << " (-1+COLS)%COLS=" << ((-1+COLS)%COLS) << endl; // init dp dp[(-1+K)%K][(-1+COLS)%COLS] = true; cout << "begin init2 dp ..." << endl; for (int i=0; i<(A-B); ++i) { dp[i%K][(-1+COLS)%COLS] = islower(a[i]) and dp[(i-1+K)%K][(-1+COLS)%COLS]; } cout << "begin updating dp ..." << endl; // update dp for (int j=0; j<B; ++j) { for (int i=j; i<=j+A-B; ++i) { // compute each item of dp[i][j] dp[i%K][j%COLS] = dp[(i-1+K)%K][(j-1+COLS)%COLS] and (toupper(a[i]) == b[j]); if (i-1>=j) dp[i%K][j%COLS] = dp[i%K][j%COLS] or dp[(i-1+K)%K][j%COLS] and islower(a[i]); // cout << "dp[" << i << "][" << j << "]=" << dp[i%K][j%COLS] << endl; } } cout << "outputing result : dp[" << A-1 << "][" << B-1 << "]=" << dp[(A-1)%K][(B-1)%COLS] << endl; if (dp[(A-1)%K][(B-1)%COLS]) return "YES"; else return "NO"; }
+ 0 comments here is a solution with time complexity
O(|b|*k)
, wherek = |a|-|b|+1
. So when both strings have length close to equal, the run time is close toO(N)
./* given a[0..i] matches to b[0..j], what if a[0..i+1] to b[0..j+1]? define dp[i][j] is either true of false, meaning the matching result between a[0..i] to b[0..j]. then dp[i][j] = dp[i-1][j-1] and toupper(a[i]) == b[j] or dp[i-1][j] and islower(a[i]) note that dp[i][j] = false for all i<j. the final answer is dp[A-1][B-1], where |a|=A and |b|=B so for any dp[i][j], i-j > (A-1)-(B-1) or i > j+A-B are not necessary now we can update dp as follow for j=[0...B) for i=[j...j+A-B] update dp[i][j] initially dp[-1][-1] = true dp[i][-1] = dp[i-1][j] and islower(a[i]) */ string abbreviation(string a, string b) { const int A = a.size(); const int B = b.size(); if (A < B) return "NO"; // size of dp array const int K = A-B+1; constexpr int COLS = 2; vector<vector<bool>> dp(K, vector<bool>(COLS, false)); cout << "begin init dp ... (-1+K)%K=" << ((-1+K)%K) << " (-1+COLS)%COLS=" << ((-1+COLS)%COLS) << endl; // init dp dp[(-1+K)%K][(-1+COLS)%COLS] = true; cout << "begin init2 dp ..." << endl; for (int i=0; i<(A-B); ++i) { dp[i%K][(-1+COLS)%COLS] = islower(a[i]) and dp[(i-1+K)%K][(-1+COLS)%COLS]; } cout << "begin updating dp ..." << endl; // update dp for (int j=0; j<B; ++j) { for (int i=j; i<=j+A-B; ++i) { // compute each item of dp[i][j] dp[i%K][j%COLS] = dp[(i-1+K)%K][(j-1+COLS)%COLS] and (toupper(a[i]) == b[j]); if (i-1>=j) dp[i%K][j%COLS] = dp[i%K][j%COLS] or dp[(i-1+K)%K][j%COLS] and islower(a[i]); // cout << "dp[" << i << "][" << j << "]=" << dp[i%K][j%COLS] << endl; } } cout << "outputing result : dp[" << A-1 << "][" << B-1 << "]=" << dp[(A-1)%K][(B-1)%COLS] << endl; if (dp[(A-1)%K][(B-1)%COLS]) return "YES"; else return "NO"; }
Load more conversations
Sort 580 Discussions, By:
Please Login in order to post a comment