Leetcode 2266. Count Number of Texts

[Woodyiiiiiii]

这道题跟91.Decode Ways是一样的思路。

建立一维dp数组，范围0～n+1，dp[i]代表i下标结尾的字符串的texts的可能数量。

重点是递推方程是什么？dp[i]跟dp[i - 1] ...的关系是什么？可以想到，如果i位置的字符与i-1的字符不等，那么dp[i]=dp[i-1]；如果相等，则说明两个字符可以生成新的一个字符了，此时dp[i]=dp[i-1] + dp[i-2]；以此类推，最大可能是4。

class Solution {
    public int countTexts(String pressedKeys) {
        
        int mod = 1000000007;
        int n = pressedKeys.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1] % mod;
            if (i > 1 && pressedKeys.charAt(i - 1) == pressedKeys.charAt(i - 2)) {
                dp[i] = (dp[i] + dp[i - 2]) % mod;
                if (i > 2 && pressedKeys.charAt(i - 1) == pressedKeys.charAt(i - 3)) {
                    dp[i] = (dp[i] + dp[i - 3]) % mod;
                    if(i > 3 && (pressedKeys.charAt(i-1) == '7' || pressedKeys.charAt(i-1) == '9') 
                        && pressedKeys.charAt(i-1) == pressedKeys.charAt(i-4)) {
                        dp[i] = (dp[i] + dp[i-4]) % mod;
                    }
                }
            }
        }
        
        return dp[n];
        
    }
}

---

参考资料：

• https://leetcode.com/problems/count-number-of-texts/discuss/2017753/Simple-O(N)-single-pass-solution