---
title: "Wildcard Matching"
author: "KickCode"
date: "2015-12-24T01:36:18Z"
tags: []
categories: ["编程语言"]
slug: "wildcard-matching"
draft: false
lastmod: "2015-12-24T01:39:47Z"
id: 2266123
url: "https://kickcode.iteye.com/blog/2266123"
---

**Wildcard Matching**
给定两个字符串p和q，判断两个字符串是否匹配。规则是：‘*’可以代表任意长度的字符串，也可以代表空串；‘?’代表任意单个的字符串。
例如：
isMatch("aa", "a") → false
isMatch("aa", "aa") → true
isMatch("aaa", "aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

这是leetcode中一道偏难的题目，我认为它属于LCS的变形，属于二维动态规划的问题。解决它我们主要要分析当前字符能代表什么。既然是二维的动态规划问题，我们创建一个二维的布尔型数组result，如果两个字符串都为空时，返回true，因此result = true; 接着我们还要继续初始化数组的第一行，也就是result*，当wildcard的当前字符为‘*’时，result*= true;当遇到不为’*'我们终止数组的初始化。

接下来我们找出状态转移方程。如果当然字符为’*‘时，我们即可以把它当做空字符也可以让它代替<span style="color:red">待匹配字符串</span>的从当前字符开始到后面所有的字符，因此此时的动态转移方程为：result* = result || result*，(cur == '*')；如果当前字符不为’*'时，如果cur等于<span style="color:red">待匹配字符串</span>的当前字符或者cur等于’?‘时它们就可以匹配，与此同时，我们还要考虑上一个状态，当(cur != '*') 时的递推式为：result* = result && (cur == '?' || cur == s.charAt(i - 1))。

有了初始化和递推式，代码就写出来了，代码如下：

```java

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] result = new boolean[m + 1][n + 1];
        result[0][0] = true;
        for(int i = 1; i <= n; i++) {
            if(p.charAt(i - 1) == '*')
                result[0][i] = true;
            else
                break;
        }
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                char cur = p.charAt(j - 1);
                if(cur != '*') {
                    result[i][j] = result[i - 1][j - 1] && (cur == '?' || cur == s.charAt(i - 1));
                } else {
                    result[i][j] = result[i - 1][j] || result[i][j - 1];
                }
            }
        }
        return result[m][n];
    }
}

```