JAVA||recursion->memoization->tabulation
\n\n\n1.try out all possible ways to count total number texts possible--->one possible way to solve this problem is using recursion as shown in the above image\
![image](https://assets.leetcode.com/users/images/19286831-7186-4092-8ee7-3c4386e4f536_1708066427.641053.jpeg)\n\n\n1.try out all possible ways to count total number texts possible--->one possible way to solve this problem is using recursion as shown in the above image\n2. later we found that overlapping subproblems occurs, therefore we apply dp. that can be converted to tabulation later\n3. we cannot do space optimization here\n//how to code\n1.we stand at particular index and find out possible combinations, so we require only two arguments string and index. f(s,index) returns number of combinations possible from index to s.length().\n2.consider f(222233), number-2 has only 3 letters,, so it could be //2,22233//22,2233//222,233//\n3.we initialize ans=0 and sum up the number of combinations possible from f(22233), f(2233), f(233)\n4.consider f(22233),,again number-2 has only 3 letters,, it could b //2,2233//22,233//222,33//\n5.sum up the number of combinations possible from f(2233), f(233), f(33)\n\nRECURSION : timelimit exceeded\n\nclass Solution {\n\tint mod=1000000007;\n\tpublic int solve(String s,int index)\n\t{\n\t\tif(index==s.length())\n\t\treturn 1;\n\t\tint ans=0;\n\t\tint maxPress=(s.charAt(index)==\'7\'||s.charAt(index)==\'9\')?4:3;\n\t\tfor(int i=index;i<s.length()&&i<index+maxPress&&s.charAt(i)==s.charAt(index);i++)\n\t\tans=(ans+solve(s,i+1))%mod;\n\t\treturn ans;\n\t}\n\tpublic int countTexts(String s) {\n\t\treturn solve(s,0);\n\t}\n}\n\nMEMOIZATION(accepted): add dp to recursion code\n\nclass Solution \n{\n\tint mod=1000000007;\n\tpublic int solve(String s,int index,int dp[])\n\t{\n\t\tif(index==s.length())\n\t\treturn 1;\n\t\tif(dp[index]!=-1)\n\t\treturn dp[index];\n\t\tint ans=0;\n\t\tint maxPress=(s.charAt(index)==\'7\'||s.charAt(index)==\'9\')?4:3;\n\t\tfor(int i=index;i<s.length()&&i<index+maxPress&&s.charAt(i)==s.charAt(index);i++)\n\t\tans=(ans+solve(s,i+1,dp))%mod;\n\t\treturn dp[index]=ans;\n\t}\n\tpublic int countTexts(String s)\n\t{\n\t\tint dp[]=new int[s.length()];\n\t\tArrays.fill(dp,-1);\n\t\treturn solve(s,0,dp);\n\t}\n}\n\ntabulation: just add one forloop ..rest is same\n\nclass Solution \n{\n\tint mod=1000000007;\n\tpublic int countTexts(String s) {\n\tint dp[]=new int[s.length()+1];\n\tdp[s.length()]=1;\n\tfor(int index=s.length()-1;index>=0;index--)\n\t{\n\t\t\tint ans=0;\n\t\t\tint maxPress=(s.charAt(index)==\'7\'||s.charAt(index)==\'9\')?4:3;\n\t\t\tfor(int i=index;i<s.length()&&i<index+maxPress&&s.charAt(i)==s.charAt(index);i++)\n\t\t\tans=(ans+dp[i+1])%mod;\n\t\t\tdp[index]=ans;\n\t\t}\n\t\treturn dp[0];\n\t}\n}
['Dynamic Programming']