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.
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 matchingresult 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|=Bso for any dp[i][j], i-j > (A-1)-(B-1) or i > j+A-B are not necessarynow we can update dp as followfor j=[0...B) for i=[j...j+A-B] update dp[i][j]initiallydp[-1][-1] = truedp[i][-1] = dp[i-1][j] and islower(a[i]) */stringabbreviation(stringa,stringb){constintA=a.size();constintB=b.size();if(A<B)return"NO";// size of dp arrayconstintK=A-B+1;constexprintCOLS=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 dpdp[(-1+K)%K][(-1+COLS)%COLS]=true;cout<<"begin init2 dp ..."<<endl;for(inti=0;i<(A-B);++i){dp[i%K][(-1+COLS)%COLS]=islower(a[i])anddp[(i-1+K)%K][(-1+COLS)%COLS];}cout<<"begin updating dp ..."<<endl;// update dpfor(intj=0;j<B;++j){for(inti=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]ordp[(i-1+K)%K][j%COLS]andislower(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";elsereturn"NO";}
Abbreviation
You are viewing a single comment's thread. Return to all 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.