Discussion on Abbreviation Challenge

Sort 580 Discussions, By:

6 days ago+ 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

2 weeks ago+ 0 comments

Here is problem solution - https://programs.programmingoneonone.com/2021/03/hackerrank-abbreviation-solution.html

3 weeks ago+ 1 comment

In Sample Test 2, the second test case: case: beFgH EFG Expected Output: NO

How does it happen?

4 weeks ago+ 0 comments

here is a solution with time complexity O(|b|*k), where k = |a|-|b|+1. So when both strings have length close to equal, the run time is close to O(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";
}

4 weeks ago+ 0 comments

here is a solution with time complexity O(|b|*k), where k = |a|-|b|+1. So when both strings have length close to equal, the run time is close to O(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