leetcode:44. 通配符匹配

「爱情、让人受尽委屈。」 2022-04-12 09:52 220阅读 0赞

## 题目: ##

给定一个字符串 (s) 和一个字符模式 § ，实现一个支持 ‘?’ 和 ‘\*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。  
‘\*’ 可以匹配任意字符串（包括空字符串）。  
两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。  
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 \*。

## 分析: ##

采用动态规划,设置二维数组记录s截取长度为i的部分和p截取长度为j的部分是否匹配,填充该二维数组

## 代码: ##

public boolean isMatch(String s, String p) {
    
    		// 动态规划,dp[i][j]表示记录s截取长度为i的字符串和p截取长度j的字符串是否满足匹配要求
    		boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
    
    		// 设置初始状态,都为0时为true
    		dp[0][0] = true;
            
            // 处理p以*开头的情况
            for (int i = 0; i < p.length(); i++){
                if (dp[0][i] && p.charAt(i) == '*'){
                    dp[0][i + 1] = true;
                }
            }
    
    		for (int i = 1; i <= s.length(); i++) {
    			for (int j = 1; j <= p.length(); j++) {
    				// 如果p的j-1位为*,则有三种情况
    				// 1.dp[i-1][j-1]为true表示s长度为i-1的前部分和p长度为j-1的前部分满足匹配要求,则只需要使新的一位字符匹配*,显然满足
    				// 2.dp[i - 1][j]为true表示s长度为i-1的前部分和p长度为j的前部分满足匹配要求,因为*可以匹配任意位数任意字符,显然也满足
    				// 3.dp[i][j - 1]为true表示s长度为i的前部分和p长度为j-1的前部分满足匹配要求,因为*可以匹配空字符串,所以也应满足
    				if (p.charAt(j - 1) == '*') {
    					dp[i][j] = dp[i - 1][j - 1] || dp[i - 1][j] || dp[i][j - 1];
    				} else {
    					//如果p的j-1位不为*,则只有在s长度为i的前部分和p长度为j-1的前部分满足匹配要求并且s和p新的一位相等或p新的一位为?才满足匹配要求
    					dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?');
    				}
    			}
    		}
    
    		return dp[s.length()][p.length()];
    	}

## 效率: ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]

## 总结: ##

效率很慢,需要优化,应有其他做法

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]: /images/20220412/94d0bf3e2e6f44bb85b0753dcedc782b.png