使用动态规划统计给定字符串的合法解码组合数（Java实现）

按照题目给出的动态规划提示，直接将子问题定义为字符串前缀的解码总数：

• 定义dp[i]为输入字符串前i个字符组成的子串，对应的合法解码序列总数
• 边界初始值：dp[0] = 1，代表长度为0的空前缀只有1种解码方式（不选取任何字符），作为递推的基准值
• 递推规则：对每个位置i（即处理到第i个字符），遍历所有给定的合法编码：
  1. 记当前编码长度为codeLen，编码值为codeVal
  2. 如果i < codeLen，说明当前前缀长度比编码短，不可能匹配，直接跳过
  3. 截取当前前缀末尾长度为codeLen的子串，如果和codeVal完全相等，说明可以把这个编码放在解码序列的最后一位，此时dp[i] += dp[i - codeLen]——即前i-codeLen个字符的所有合法解码，拼接当前编码后都是合法序列

题目给出的所有编码最长为4位，每个位置最多向前检查4位即可，不需要多余遍历。这种实现把每个前缀的计算结果存在dp数组里，不会像纯递归那样重复计算相同子串的结果，时间复杂度是线性的，长输入也能快速算出结果。

import java.util.HashSet;
import java.util.Set;

public class DecodeCounter {
    // 存储所有合法编码，HashSet可实现O(1)复杂度的匹配判断
    private static final Set<String> VALID_CODES = new HashSet<>();
    static {
        VALID_CODES.add("0");     // A
        VALID_CODES.add("00");    // B
        VALID_CODES.add("001");   // C
        VALID_CODES.add("010");   // D
        VALID_CODES.add("0010");  // E
        VALID_CODES.add("0100");  // F
        VALID_CODES.add("0110");  // G
        VALID_CODES.add("0001");  // H
    }

    public static int countDecodings(String s) {
        int n = s.length();
        // dp数组，dp[i]对应前i个字符的合法解码总数
        int[] dp = new int[n + 1];
        dp[0] = 1; // 空串基准值

        for (int i = 1; i <= n; i++) {
            for (String code : VALID_CODES) {
                int codeLen = code.length();
                if (i >= codeLen) {
                    // 截取末尾长度为codeLen的子串做匹配
                    String sub = s.substring(i - codeLen, i);
                    if (sub.equals(code)) {
                        dp[i] += dp[i - codeLen];
                    }
                }
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        // 测试用例1：输入00100，预期输出5
        System.out.println(countDecodings("00100"));
        // 测试用例2：输入1111，预期输出0
        System.out.println(countDecodings("1111"));
        // 测试用例3：题目给出的长输入，预期输出5567
        String longInput = "000100100010010000100100001001100";
        System.out.println(countDecodings(longInput));
    }
}

• 相比原纯递归实现，该版本无重复计算：每个前缀子串的解码数仅计算一次，时间复杂度为O(n)（n为输入字符串长度，每个位置固定遍历8个合法编码，计算量和输入长度成正比）
• 所有测试用例运行结果和题目参考值完全匹配：
  • 输入00100输出5，对应ADA、AF、CAA、CB、EA五种解码
  • 输入1111输出0，无合法解码
  • 输入题目给出的长参考字符串输出5567，和参考结果一致
• 如果后续编码表有调整，仅需修改VALID_CODES集合内的编码值即可，不需要改动核心递推逻辑。

内容的提问来源于stack exchange，提问作者kiku89