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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Abbreviation
  5. Discussions

Abbreviation

Problem
Submissions
Leaderboard
Discussions
Editorial

    You are viewing a single comment's thread. Return to all comments →

  • wilsonthongwk
    3 months 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";
    }
    
    0|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy