Memoization and Recursion Implementation in Hackerrank Abbreviation Problem In Golang

321 Views Asked by At

So I was attempting to do the Hackerrank Abbreviation problem by using recursion and memoization. It was fine when the test case is short but when the string started to get large, I found that my code ends halfway (according to what i saw in the debug window that Hackkerrank provides) so i got 5 of 16 test cases wrong. I couldn't understand why it happened, hope somebody could help me debugging the code and tell me what did I miss :(. It has been bugging for two days now. Sorry for my bad english btw. Here i provide the question and my code,

Abbreviation Problem Hackerrank

func abbreviation(a string, b string) string {
    // Write your code here
    memoization := make(map[string]bool)
    result := rec(a,b,memoization)
    if result {
        return "YES"
    }else{
        return "NO"
    }
}

func rec(a string, b string, memoization map[string]bool) bool {
    fmt.Println("a=", a,"b=",b)
    baseB := ""
    var result bool
    //check
    if len(a)<len(b){//check_len
        return false
    }
    if _,ok:=memoization[a+"#"+b]; ok{//check_memoization
        return memoization[a+"#"+b]
    }
    if b==baseB{//check_leaf
        for i:=0; i<len(a); i++{
            if strings.ToUpper(string(a[0]))==string(a[0]){
                return false
            }
        }
        return true
    }
    //recursion
    if strings.ToUpper(string(a[0])) == string(a[0]){
        if b[0]==a[0]{
            a1 := a[1:]
            b1 := b[1:]
            result = rec(a1,b1,memoization)
        }else{
            return false 
        }
    }else{
        a1 := a[1:]
        a2 := strings.ToUpper(string(a[0])) + a[1:]
        if strings.ToUpper(string(a[0])) == string(b[0]){
        recursive1 := rec(a1,b,memoization)
        recursive2 := rec(a2,b,memoization)
        result = recursive1 || recursive2
        }else{
        recursive1 := rec(a1,b,memoization)
        recursive2 := false
        result = recursive1 || recursive2
        }
    }
    memoization[a+"#"+b]=result
    return result 
}
0

There are 0 best solutions below