Discussion on Abbreviation Challenge

Sort 585 Discussions, By:

4 weeks ago+ 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

3 months ago+ 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";

}

3 months ago+ 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 ?

3 months ago+ 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";
    }

4 months ago+ 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