JAVA | MEMO | EXPLAINED | O(N)
\nclass Solution {\n    public int countTexts(String pressedKeys) {\n        int[] memo=new int[pressedKeys.length()];\n        \n        return dfs(pressedKeys
```\nclass Solution {\n    public int countTexts(String pressedKeys) {\n        int[] memo=new int[pressedKeys.length()];\n        \n        return dfs(pressedKeys,memo,0);\n    }\n    \n    public int dfs(String pk,int[] memo,int index){\n        if(index==pk.length())  //if end of string is reached that is one permutation\n            return 1;\n        \n        if(memo[index]!=0)      //if countof permutations for that index is already calculated\n            return memo[index];\n        \n        int count=0;\n        for(int i=0;i<4;i++){   //max we need to go four index forward\n            //for only button 7 and 9 we have 4 charcters\n            if(pk.charAt(index)!=\'7\' && pk.charAt(index)!=\'9\' && i==3)  \n                break;\n            \n            if(index+i>=pk.length())    //if end index goes out of bounds\n                break;\n              \n            if(i!=0){  \n                //if adjacent characters are not same\n                if(pk.charAt(index+i)!=pk.charAt(index+i-1))    \n                    break;\n            }\n            \n            count+=dfs(pk,memo,index+i+1);  //recursive call for remaining string\n            count%=1000000007;\n                \n        }\n        \n        memo[index]=count;  //store the calculated value for this index\n        return count;\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Java']