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
}