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
+ 1 comment Test Case:
3
AbCdE
AFE
beFgH
EFG
beFgH
EFH
Expected value:
NO
NO
YES
Why find "EFG" in "beFgH" expected to be NO?
beFgH -> bEFGH -> EFG
+ 0 comments Can Anybody help why my code is failing for tc12 and 14. I userd memoization. Thanks
int dp[1001][1001]; string s1,s2; int m,n; bool solve(int i,int j){ if(i==m) return j==n; if(m-i<n-j) return 0; if(j==n and i!=m){ for(;i<m;i++){ if(isupper(s1[i])) return 0; } return 1; } if(isupper(s1[i]) and s1[i]!=s2[j]) return 0; if(dp[i][j]!=-1) return dp[i][j]; bool b1=solve(i+1,j); if(toupper(s1[i])==s2[j]) b1=b1 or solve(i+1,j+1); dp[i][j]=b1?1:0; return b1; } string abbreviation(string a, string b) { memset(dp,-1,sizeof(dp)); s1=a,s2=b; m=a.size(),n=b.size(); return (solve(0,0))?"YES":"NO"; }
+ 0 comments In test case 8 the 5th pattern expects a "no". I have tabulated the number of upper and lower case letters in variable "a" and "b" and can't see why this cannot be matched. In no case do I find an upper case letter count in variable "a" higher than b, and there's enough upper case paired with lower case letters in "a" to satisfy the number of uppercase letters needed in "b". The rest of lowercase letters can be dropped. Am I missing something ?
+ 0 comments Java Solution:
public static String abbreviation(String a, String b) { char[] s1 = a.trim().toCharArray(); char[] s2 = b.toUpperCase().trim().toCharArray(); int rows = s2.length; int cols = s1.length; boolean[][] dp = new boolean[rows+1][cols+1]; dp[0][0] = true; //Fill the first col for(int row = 1; row<=rows; row++){ dp[row][0] = false; } //Fill the first row for(int col = 1; col <= cols; col++){ if(Character.isLowerCase(s1[col-1])) dp[0][col] = dp[0][col-1]; else dp[0][col] = false; } for(int row = 1; row <= rows; row++){ for(int col = 1; col <= cols; col++){ if(Character.toUpperCase(s1[col - 1]) == s2[row-1]){ if(Character.isLowerCase(s1[col-1])){ dp[row][col] = dp[row-1][col-1]?dp[row-1][col-1]: dp[row][col-1]; }else dp[row][col] = dp[row-1][col-1]; } else if(Character.isLowerCase(s1[col-1])) dp[row][col] = dp[row][col-1]; else dp[row][col] = false; } } return dp[rows][cols]? "YES" : "NO"; }
+ 0 comments My Code
def abbreviation(a, b): # Write your code here dp = [[False for _ in range(len(b)+1)] for _ in range(len(a)+1)] dp[0][0] = True for i in range(len(a)): for j in range(len(b)+1): if dp[i][j]: if j < len(b) and a[i].upper() == b[j]: dp[i+1][j+1] = True if a[i].islower(): dp[i+1][j] = True return 'YES' if dp[len(a)][len(b)] else 'NO'
Load more conversations
Sort 585 Discussions, By:
Please Login in order to post a comment