JAVA | Count & DP bottom-up
1, count the numbers in the given string, \npressedKeys 22235555\ncompressed  3 of 2s ; 1 of 3s, 4 of 5s\n\n2, calculate 2 dp arrays for the number with 3 possi
1, count the numbers in the given string, \npressedKeys 22235555\ncompressed  3 of 2s ; 1 of 3s, 4 of 5s\n\n2, calculate 2 dp arrays for the number with 3 possible letters and 4 possible letters till the maximum \ndp3[m] is the possible ways of keys for m same numbers (which has 3 letters on the button)\ndp4[m] is the possible ways of keys for m same numbers (which has 4 letters on the button)\n\ndp3: 0,1,2,4,7,...\ndp4: 1,1,2,4,8,...\n\n3, multiply the possibilitis to get the result.\n\n\n```\nclass Solution {\n    private int MOD = 1000000007;\n    public int countTexts(String pressedKeys) {\n        List<List<Integer>> list = new ArrayList<>();\n        int maxLen = 0;\n        char prevCh = \'a\';\n        int curLen = 0;\n        for(int i=0;i<pressedKeys.length();i++){\n            if(pressedKeys.charAt(i) == prevCh){\n                curLen++;\n                maxLen = Math.max(maxLen,curLen);\n            }else{\n                if(curLen >0){\n                    list.add(Arrays.asList(curLen,prevCh-\'0\'));\n                }\n                curLen = 1;\n                prevCh = pressedKeys.charAt(i);\n            }\n        }\n        list.add(Arrays.asList(curLen,prevCh-\'0\'));\n        \n       // System.out.println(list);        \n        \n        long[] dp3 = new long[Math.max(maxLen+1,5)];\n        long[] dp4 = new long[Math.max(maxLen+1,5)];             \n        \n        dp3[1] = 1;\n        dp3[2] = 2;\n        dp3[3] = 4;\n        \n        dp4[0] = 1;\n        dp4[1] = 1;\n        dp4[2] = 2;\n        dp4[3] = 4;\n\n        for(int i=4;i<dp3.length;i++){            \n            dp3[i] = ((long)dp3[i-1]+dp3[i-2]+dp3[i-3])%MOD;\n            dp4[i] = ((long)dp4[i-1]+dp4[i-2]+dp4[i-3]+dp4[i-4])%MOD;\n        }\n        \n        //System.out.println(Arrays.toString(dp3));\n        //System.out.println(Arrays.toString(dp4));\n        \n        long ret = 1;\n        for(List<Integer> num:list){\n            long nextVal = 1;\n            if(num.get(1)==7 || num.get(1)==9){\n                nextVal = dp4[num.get(0)];\n            }else            {\n                nextVal = dp3[num.get(0)];\n            }\n            ret =  (ret*nextVal)%MOD;\n        }\n        \n        return (int)ret;\n    }\n}\n```
[]