I am solving alpha code on spoj.I wrote the below code and it is give wrongans for the sample test case.Please teach me how to solve the problem using recursion only.Thanks
def issafe(pos):
global n
if pos+1<n:
return True
return False
def solve(pos,st):
global n
if pos>n-1:
return 0
z=0
if issafe(pos):
z=st[pos]*10+st[pos+1]
x=0
if st[pos]<=26:
x=1+solve(pos+1, st)
y=0
if z>=10 and z<=26 :
y=1+solve(pos+2, st)
return x+y
while(True):
nt=input()
n=len(nt)
if nt=='0':
break
st=[]
for i in nt:
st.append(int(i))
ans=solve(0, st)
print(ans)
see, the basic procedure is to use a for loop, so recursion can be used, but i don’t think just a recursive approach will help you with this.
Consider the case 11
Number of ways to represent 11 is 2: AA and K. But your code is printing 3. That’s because you are adding 1 to the count every time you call the function.
what you have to do is for every i in string s, if s[i]!=‘0’, count[i]=1(count gives number of possibilities at that index)
now, there are cases where 2 characters can be used to represent an alphabet, so, we need to add all such cases together(in above example 11) hence we add count[i-2] to count[i]
why i-2? because after i-2, the i-1th character and i th character form the new alphabet, so its a new arrangement added to all the previous arrangements.
take another example 111
here c[0]=1 c[1]=1+1 c[2]=1+2…hence ans is 3
for dual possibilities such as this right at the first index, i would advise u to add a space in front of the string ie ‘111’ → ’ 111’