解题思路

这是一个字符串匹配问题，可以使用动态规划来解决。关键点：

  1. 状态定义：

    • 表示字符串 的前 个字符是否能被字符串 的前 个字符匹配。

  2. 状态转移：

    • 如果当前字符匹配（ 或 $B[j-1] == '.'），则：
    • 如果 是 '*'，则：
      • // '*'表示前一个字符出现0次
      • // '*'表示前一个字符出现1次或多次（前一个字符必须与A[i-1]匹配）

  3. 初始化：

    • ，表示两个空字符串匹配。
    • 处理 中 '*' 的情况，初始化 。

代码

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class WildMatch {
public:
    bool chkWildMatch(string A, int lena, string B, int lenb) {
        vector<vector<bool>> dp(lena + 1, vector<bool>(lenb + 1, false));
        dp[0][0] = true;  // 两个空字符串匹配
        
        // 初始化B的情况
        for (int j = 1; j <= lenb; j++) {
            if (B[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];  // '*'表示前一个字符出现0次
            }
        }
        
        // 动态规划填表
        for (int i = 1; i <= lena; i++) {
            for (int j = 1; j <= lenb; j++) {
                if (A[i - 1] == B[j - 1] || B[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];  // 当前字符匹配
                } else if (B[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2];  // '*'表示前一个字符出现0次
                    if (A[i - 1] == B[j - 2] || B[j - 2] == '.') {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];  // '*'表示前一个字符出现1次或多次
                    }
                }
            }
        }
        
        return dp[lena][lenb];
    }
};

int main() {
    WildMatch wildMatch;
    string A = "abcd";
    string B = ".*";
    int lena = A.length();
    int lenb = B.length();
    
    bool result = wildMatch.chkWildMatch(A, lena, B, lenb);
    cout << (result ? "true" : "false") << endl;  // 应该输出 true
    
    return 0;
}

import java.util.*;

public class WildMatch {
    public boolean chkWildMatch(String A, int lena, String B, int lenb) {
        boolean[][] dp = new boolean[lena + 1][lenb + 1];
        dp[0][0] = true;  // 两个空字符串匹配
        
        // 初始化B的情况
        for (int j = 1; j <= lenb; j++) {
            if (B.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];  // '*'表示前一个字符出现0次
            }
        }
        
        // 动态规划填表
        for (int i = 1; i <= lena; i++) {
            for (int j = 1; j <= lenb; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1) || B.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];  // 当前字符匹配
                } else if (B.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2];  // '*'表示前一个字符出现0次
                    if (A.charAt(i - 1) == B.charAt(j - 2) || B.charAt(j - 2) == '.') {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];  // '*'表示前一个字符出现1次或多次
                    }
                }
            }
        }
        
        return dp[lena][lenb];
    }
}

# -*- coding: utf-8 -*-

class WildMatch:
    def chkWildMatch(self, A, lena, B, lenb):
        dp = [[False] * (lenb + 1) for _ in range(lena + 1)]
        dp[0][0] = True  # 两个空字符串匹配
        
        # 初始化B的情况
        for j in range(1, lenb + 1):
            if B[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]  # '*'表示前一个字符出现0次
        
        # 动态规划填表
        for i in range(1, lena + 1):
            for j in range(1, lenb + 1):
                if A[i - 1] == B[j - 1] or B[j - 1] == '.':
                    dp[i][j] = dp[i - 1][j - 1]  # 当前字符匹配
                elif B[j - 1] == '*':
                    dp[i][j] = dp[i][j - 2]  # '*'表示前一个字符出现0次
                    if A[i - 1] == B[j - 2] or B[j - 2] == '.':
                        dp[i][j] = dp[i][j] or dp[i - 1][j]  # '*'表示前一个字符出现1次或多次
        
        return dp[lena][lenb]

算法及复杂度

  • 算法：动态规划
  • 时间复杂度：，需要填充 的 dp 表
  • 空间复杂度：，需要 的 dp 数组