动态规划法解决字符串匹配问题java语言

字符串匹配问题可以使用动态规划法进行解决。具体来说，可以使用一个二维数组dp[i][j]表示文本串中前i个字符与模式串中前j个字符是否匹配。其中，dp[0][0]表示两个空串匹配，dp[i][0]表示空模式串与任何文本串都匹配，dp[0][j]则表示文本串为空，只有当模式串中前j个字符均为*时才为匹配。

状态转移方程如下：

1. 当模式串第j个字符是*时：

dp[i][j] = dp[i][j-1] || dp[i-1][j]

解释：*可以表示空字符或者匹配一个或多个字符。dp[i][j-1]表示*匹配0个字符，dp[i-1][j]表示*匹配一个或多个字符。

2. 当模式串第j个字符不是*时：

dp[i][j] = dp[i-1][j-1] && (text[i-1] == pattern[j-1] || pattern[j-1] == '?')

解释：当模式串第j个字符不是*时，只有当文本串中第i个字符与模式串中第j个字符相同或者模式串中第j个字符为?时才能匹配。

最终的匹配结果为dp[text_len][pattern_len]，其中text_len和pattern_len分别为文本串和模式串的长度。

以下是使用Java语言实现字符串匹配问题的动态规划法的示例代码：

public class StringMatch {
    public static boolean isMatch(String text, String pattern) {
        int text_len = text.length();
        int pattern_len = pattern.length();
        
        // 初始化dp数组
        boolean[][] dp = new boolean[text_len+1][pattern_len+1];
        dp[0][0] = true;

        // 处理dp数组的第一行
        for (int j = 1; j <= pattern_len; j++) {
            if (pattern.charAt(j-1) == '*') {
                dp[0][j] = dp[0][j-1];
            }
        }

        // 处理dp数组的其余部分
        for (int i = 1; i <= text_len; i++) {
            for (int j = 1; j <= pattern_len; j++) {
                if (pattern.charAt(j-1) == '*') {
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j-1] && (text.charAt(i-1) == pattern.charAt(j-1) || pattern.charAt(j-1) == '?');
                }
            }
        }

        // 返回匹配结果
        return dp[text_len][pattern_len];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入文本串：");
        String text = sc.nextLine();
        System.out.print("请输入模式串：");
        String pattern = sc.nextLine();
        if (isMatch(text, pattern)) {
            System.out.println("匹配成功！");
        } else {
            System.out.println("匹配失败！");
        }
    }
}