力扣2266. 统计打字方案数随笔

"永远、永远、永远不要放弃。"——温斯顿·丘吉尔

题目

Alice 在给 Bob 用手机打字。数字到字母的 对应 如下图所示。

为了 打出 一个字母，Alice 需要 按 对应字母 i 次，i 是该字母在这个按键上所处的位置。

• 比方说，为了按出字母 's' ，Alice 需要按 '7' 四次。类似的， Alice 需要按 '5' 两次得到字母  'k' 。
• 注意，数字 '0' 和 '1' 不映射到任何字母，所以 Alice 不 使用它们。

但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息 。

• 比方说，Alice 发出的信息为 "bob" ，Bob 将收到字符串 "2266622" 。

给你一个字符串 pressedKeys ，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息 。

由于答案可能很大，将它对  取余 后返回。

分析

        此题为动态规划问题，但是笔者做的时候人又晕了，只会回溯，O(∩_∩)O，在此记录一下。

        从图中可以看出，每个数字对应三或四个字母，因此对于一串相同的数字，可以以单个、两个、三个或四个解析。用dp[i]表示字符串前i个字符可以发出的文字信息，空字符串为一种答案，因此可以得到以下的转移方程：

        

解答

回溯（C++）

class Solution {
public:
    int countTexts(string pressedKeys) {
        vector<string> dict={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        vector<int> store(pressedKeys.length(),-1);
        return dfs(store,dict,pressedKeys,0);
    }

    int dfs(vector<int>& store, vector<string>& dict, string& pressedKeys, int index){
        if (index==pressedKeys.length()){
            return 1;
        }
        if (store[index]!=-1){
            return store[index];
        }
        int ans=0;
        int MOD=1e9+7;
        int cur=pressedKeys[index]-'0';
        for (int i=0;i<dict[cur].length();i++){
            if (index+i>=pressedKeys.length()||pressedKeys[index+i]!=pressedKeys[index]){
                break;
            }
            ans=(ans+dfs(store,dict,pressedKeys,index+i+1))%MOD;
        }
        store[index]=ans;
        return ans;
    }
};

动态规划（Java）

class Solution {
    public int countTexts(String pressedKeys) {
        int n=pressedKeys.length();
        int MOD=1000000007;
        int[] dp=new int[n+1];
        dp[0]=1;
        for (int i=1;i<=n;i++){
            char c=pressedKeys.charAt(i-1);
            dp[i]=dp[i-1];  //单个字符
            if (i>=2&&pressedKeys.charAt(i-2)==c){  
                dp[i]=(dp[i]+dp[i-2])%MOD;  //两个连续字符
                if (i>=3&&pressedKeys.charAt(i-3)==c){  
                    dp[i]=(dp[i]+dp[i-3])%MOD;  //三个连续字符
                    if ((c=='7'||c=='9')&&i>=4&&pressedKeys.charAt(i-4)==c){
                        dp[i]=(dp[i]+dp[i-4])%MOD;  //四个连续字符
                    }
                }
            }
        }
        return dp[n];
    }
}

"那些不能记住过去的人注定要重蹈覆辙。" ——乔治·桑塔亚那

原文地址：https://blog.csdn.net/xljjjjjj/article/details/145241387

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！