首页 > 代码库 > 【leetcode刷题笔记】Wildcard Matching

【leetcode刷题笔记】Wildcard Matching

2024-07-14 03:24:59   222人阅读

Implement wildcard pattern matching with support for ‘?‘ and ‘*‘.

‘?‘ Matches any single character.‘*‘ Matches any sequence of characters (including the empty sequence).The matching should cover the entire input string (not partial).The function prototype should be:bool isMatch(const char *s, const char *p)Some examples:isMatch("aa","a") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "*") → trueisMatch("aa", "a*") → trueisMatch("ab", "?*") → trueisMatch("aab", "c*a*b") → false

题解：昨天晚上写了一晚上的递归，一直TLE。早上果断改用dp了，结果dp还TLE了好多次，真是说多了都是泪。

dp的思想很简单：用二维数组dp[s_length+1][p_length+1]记录结果。

  • 首先如果s和p都是空串的话，那么它们是匹配的，所以dp[0][0] = true;
  • 当s为空串的时候（dp中的第一行），dp[0][i] = p[i] == ‘*‘? dp[0][i-1]:false;(i=1,...,p_length);
  • 对于任意j，如果p(j-1) == ‘*‘，dp[i][j]= dp[i-1][j] || dp[i][j-1]，对应了两种情况，前一种是不匹配‘*’，后一种情况是匹配‘*‘，如下图所示：
  • 如果p(j-1) != ‘*‘，则只有p(j-1) == ‘?‘或者s(i-1) == p(j-1)的时候才有dp[i][j] = true;否则dp[i][j] = false；

开始以为这样就可以过了，事实证明I am too young too simple。这样还是会超时。要优化两个地方：

  • 数出p中不是‘*‘的字符个数，如果比s的总长度还长，那么s是没有办法匹配的，直接返回false；
  • 第二个优化让我非常无语，就是在实现循环的时候，不要每次用p.charAt(j)来取字符，要在开始用ch_p = p.charAt(j)把字符记下来，在以后的循环中就用这个，这么看来p.charAt(j)这个操作还是很耗时的，以后如果在程序中反复使用，都要把它存下来再使用。

最后AC的代码如下：

 1 public class Solution { 2     public boolean isMatch(String s, String p) { 3         int m = s.length(); 4         int n = p.length(); 5          6         int count = 0; 7         for(int indexP = 0;indexP<n;indexP++) 8             if(p.charAt(indexP) != ‘*‘) 9                 count++;10         if(count > m)11             return false;12         13         boolean[][] dp =new boolean[m+1][n+1];14         dp[0][0] = true;15         16         for(int j = 1;j<=n;j++)17         {   18             char ch_p = p.charAt(j-1);19             if(ch_p ==‘*‘ && dp[0][j-1])20                 dp[0][j]= true;21             22             for(int i= 1;i<=m;i++){23                 char ch_s = s.charAt(i-1);24                 if(ch_p ==‘*‘)25                     dp[i][j]= dp[i-1][j]|| dp[i][j-1];26                 else if(ch_p == ‘?‘ || ch_p == ch_s){27                     dp[i][j] = dp[i-1][j-1]; 28                 }29                 else30                     dp[i][j]= false; 31             }32         }33         return dp[m][n];34     }35 }

 


联系
我们