Easy Memoization | O(n) time | C++ | With Explanation | With comments
The simplest way to cache sub problems is to break this problem to :\ntotal ways=No of ways to have one alphabet * number of ways of rest of the string.\nWe don
The simplest way to cache sub problems is to break this problem to :\ntotal ways=No of ways to have one alphabet * number of ways of rest of the string.\nWe dont have length of rest of the remaining string constant...like 6+rest, 66+rest\' map to \'m\'+rest  and \'n\'+rest\' respectively.\nSo we iterate  ```No of ways to to have one alphabet```  and add  ``` number of ways of rest of the string```   in each iteration.\n```\nclass Solution {\npublic:\n    const int M=1000000007;\n    vector<int>dp;\n    int count(string &s,int i)\n    {\n        if(i==s.size())return 1;\n        if(dp[i]!=-1)return dp[i];\n        int no=3;//number of characters in the button\n        if(s[i]==\'7\'||s[i]==\'9\')no=4;\n        int ans=0,len=0;\n        for(int j=i;j<i+no&&j<s.size();j++) //looping over possible alphabets out of the consecutively same  button press.\n        {\n            if(s[j]==s[i])ans=(ans+count(s,j+1))%M;//adding number of ways to have the rest of the string\n                else break;\n        }\n        return dp[i]=ans;\n        \n    }\n    int countTexts(string s) {\n        dp.resize(s.size(),-1);\n        return count(s,0);\n    }\n};\n```\nPlease upvote if you find the solution helping.
['Memoization']