✅C++ || Recurison->Memoization->Tabulation
Method -1 [Recursion]\n\n\n\nT->O(expo)  && S->O(n) [Recursion stack space]\n\n\tclass Solution {\n\t\tpublic:\n\t\t\tint f(int i,string& k,int n){\n\t\t\t\tif(
# Method -1 [Recursion]\n\n![image](https://assets.leetcode.com/users/images/02f6d5b8-8bf7-4995-83b4-690b1269b8f0_1664275039.265253.png)\n\n**T->O(expo)  && S->O(n) [Recursion stack space]**\n\n\tclass Solution {\n\t\tpublic:\n\t\t\tint f(int i,string& k,int n){\n\t\t\t\tif(i>n) return 0;\n\t\t\t\tif(i==n) return 1;\n\t\t\t\tint a=0,b=0,c=0,d=0;\n\t\t\t\ta=f(i+1,k,n);\n\t\t\t\tif(k[i]==k[i+1]) b=f(i+2,k,n);\n\t\t\t\tif(k[i]==k[i+1] && k[i]==k[i+2]) c=f(i+3,k,n);\n\t\t\t\tif(k[i]==k[i+1] && k[i]==k[i+2] && k[i]==k[i+3] && (k[i]==\'7\' || k[i]==\'9\')) d=f(i+4,k,n);\n\t\t\t\treturn a+b+c+d;\n\t\t\t}\n\n\t\t\tint countTexts(string keys) {\n\t\t\t\tint n=keys.size();\n\t\t\t\treturn f(0,keys,n);\n\t\t\t}\n\t\t};\n\t\t\n# Method -2 [Memoization]\t\t\n![image](https://assets.leetcode.com/users/images/b8a9f735-5965-4637-81e7-4e93db57bcf0_1664275470.249758.png)\n\n**T->O(n) && S->O(n)+O(n) [Recursion stack space]**\n\n\tclass Solution {\n\tpublic:\n\t\tint mod=1e9+7;\n\t\tint f(int i,string& k,int n,vector<int>& dp){\n\t\t\tif(i>n) return 0;\n\t\t\tif(i==n) return 1;\n\t\t\tif(dp[i]!=-1) return dp[i];\n\t\t\tlong long b=0,c=0,d=0;\n\t\t\tlong long a=f(i+1,k,n,dp);\n\t\t\tif(k[i]==k[i+1]) b=f(i+2,k,n,dp);\n\t\t\tif(k[i]==k[i+1] && k[i]==k[i+2]) c=f(i+3,k,n,dp);\n\t\t\tif(k[i]==k[i+1] && k[i]==k[i+2] && k[i]==k[i+3] && (k[i]==\'7\' || k[i]==\'9\')) d=f(i+4,k,n,dp);\n\t\t\treturn dp[i]=(a+b+c+d)%mod;\n\t\t}\n\n\t\tint countTexts(string keys) {\n\t\t\tint n=keys.size();\n\t\t\tvector<int> dp(n,-1);\n\t\t\treturn f(0,keys,n,dp)%mod;\n\t\t}\n\t};\n\t\n# Method -3 [Tabulation]\t\n![image](https://assets.leetcode.com/users/images/7fbfd781-8a53-4c4a-a4a7-efc3190a9316_1664275945.1414998.png)\n\n**T->O(n) && S->O(n)**\n\n\tclass Solution {\n\tpublic:\n\t\tint mod=1e9+7;\n\t\tint countTexts(string k) {\n\t\t\tint n=k.size();\n\t\t\tvector<int> dp(n+4,0);\n\t\t\tdp[n]=1;\n\t\t\tfor(int i=n-1;i>=0;i--){\n\t\t\t\tlong long b=0,c=0,d=0;\n\t\t\t\tlong long a=dp[i+1];\n\t\t\t\tif(k[i]==k[i+1]) b=dp[i+2];\n\t\t\t\tif(k[i]==k[i+1] && k[i]==k[i+2]) c=dp[i+3];\n\t\t\t\tif(k[i]==k[i+1] && k[i]==k[i+2] && k[i]==k[i+3] && (k[i]==\'7\' || k[i]==\'9\')) d=dp[i+4];\n\t\t\t\tdp[i]=(a+b+c+d)%mod;\n\t\t\t}\n\t\t\treturn dp[0]%mod;\n\t\t}\n\t};
['Dynamic Programming', 'Recursion', 'Memoization', 'C', 'C++']