双序列型动态规划例题6 Lintcode192 (通配符匹配)Wildcard Matching

本文主要是介绍双序列型动态规划例题6 Lintcode192 (通配符匹配)Wildcard Matching，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

动态规划组成部分一：确定状态

动态规划组成部分二：转移方程

动态规划组成部分三：初始条件和边界情况

动态规划组成部分四：计算顺序

Java代码实现

    public boolean isMatch(String s, String p) {int m = s.length();int n = p.length();char[] ch1 = s.toCharArray();char[] ch2 = p.toCharArray();boolean[][] f = new boolean[m + 1][n + 1];f[0][0] = true;for (int i = 0; i <= m; i++)for (int j = 1; j <= n; j++) {if ((ch2[j - 1] != '*') && (i > 0)) {if (ch2[j - 1] == '?' || ch1[i - 1] == ch2[j - 1])f[i][j] = f[i - 1][j - 1];} else if (ch2[j - 1] == '*') {f[i][j] = f[i][j - 1];if (i > 0)f[i][j] |= f[i - 1][j];}}return f[m][n];}

这篇关于双序列型动态规划例题6 Lintcode192 (通配符匹配)Wildcard Matching的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---