精华内容
下载资源
问答
  • Wildcard Matching

    2017-01-29 10:45:23
    Wildcard Matching 题目链接:https://leetcode.com/problems...这道题还是可以用"Regular Expression Matching" 的方法,用2d的dp数组来解,空间复杂度较高。 public boolean isMatch(String s, String p) { ...
        

    Wildcard Matching

    题目链接:
    https://leetcode.com/problems...
    这道题还是可以用"Regular Expression Matching" 的方法,用2d的dp数组来解,空间复杂度较高。

        public boolean isMatch(String s, String p) {
            /* boolean dp[len(s) + 1][len(p) + 1] 
             * dp[i+1][j+1] means if s[0, i] match p[0, j]
             * function: dp[i+1][j+1] 
             *         a. p[j] = * => 1. empty: dp[i+1][j]
             *                        2. one: dp[i][j]
             *                        3. multiple: dp[i][j+1]
             *         b. p[j] = s[i] | p[j] = ? => dp[i][j]
             * start: dp[0][0] = true, dp[0][j+1] = dp[0][j] & p[j] = *
             * result: dp[len(s)][len(p)]
             */
             
             boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
             // start
             dp[0][0] = true;
             for(int j = 0; j < p.length(); j++) dp[0][j+1] = dp[0][j] & (p.charAt(j) == '*');
             
             // loop
             for(int i = 0; i < s.length(); i++) {
                 for(int j = 0; j < p.length(); j++) {
                     if(p.charAt(j) == '*') {
                         dp[i+1][j+1] = dp[i+1][j] | dp[i][j] | dp[i][j+1];
                     }
                     else if(p.charAt(j) == s.charAt(i) || p.charAt(j) == '?') dp[i+1][j+1] = dp[i][j];
                 }
             }
             return dp[s.length()][p.length()];
        }

    另一种思路是greedy,只需要O(1)的空间。和regular expression不同,这道题的star符号和前面的character没有关系,不需要一起考虑。而且star是可以匹配任何string的,"aa", "ab"都可以。所以check是否匹配的时候,只需要按位一个一个判断就行了。用两个指针i和j分别扫描s和p,loop过程中有以下几种情况:

    1. 成功匹配:s[i] == p[j] or p[j] == '?' => i++, j++

    2. 出现星号:p[j] == '*'

    3. 匹配不上:return false

    第二种情况比较麻烦,单独讨论一下。

    1. p[j]匹配0个 => j++

    2. p[j]匹配1个 => j++, i += 1

    3. p[j]匹配2个 => j++, i += 2
      ......

    可以看出来,要尝试不同的匹配个数,所以要加两个指针保存之前出现star时的i和j:stari和starj。那么每次碰到'*'的时候,都保存一下,先试下匹配0个的时候后面的字符是否可以匹配上,如果不行再试1个,2个。。重复这个过程。
    以s的长度为loop的终点,所以最后还要考虑一下p后面还有多的'*'的情况。

    时间复杂度度

    最好的情况下,没有star或者所有star都匹配0个字符,O(M+N)。
    最坏的情况下,star间隔出现且每个star都要匹配很多字符,设一个star平均匹配s里面x个字符,O(xN + M) = O(M*N)。其中,M是s的长度,N是p的长度。

        public boolean isMatch(String s, String p) {
            int i = 0, j = 0;
            int stari = -1, starj = -1;
            while(i < s.length()) {
                // 1. match
                if(j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
                    i++; j++;
                }
                // 2. star
                else if(j < p.length() && p.charAt(j) == '*') {
                    // first match 0
                    stari = i;
                    starj = ++j;
                }
                // different number that '*' matches 
                else if(stari != -1) {
                    // match number +1
                    i = ++stari;
                    j = starj;
                }
                // 3. not match and no star
                else return false;
            }
            // remove last '*' in p
            while(j < p.length() && p.charAt(j) == '*') j++;
            
            return j == p.length();
        }
    展开全文
  • 通配符匹配。简单来说就是判断字符串s和pattern字符串p是否匹配,p中的?符号表示任意一个字符,p中的*符号表示任意一个字符序列。 首先说说我自己的递推的思想: 虽然很多人说这种是动态规划的解法,但我本人并不...

    通配符匹配。简单来说就是判断字符串s和pattern字符串p是否匹配,p中的?符号表示任意一个字符,p中的*符号表示任意一个字符序列。

    首先说说我自己的递推的思想:

    虽然很多人说这种是动态规划的解法,但我本人并不认同这种说法,如果严格按照动态规划的定义划分的话,这个既没有最优子结构也没有重复计算的问题。不过不用在意这些细节了。

    设一个二维数组bp,bp[i][j]的语义是:s的前i个字符和p的前j个字符是否匹配。

    边界条件b[0][0]=true,b[0][j]=true(p的前j个字符都是*)

    我们可以求解bp[i][j]:

    如果p[j]是字母,则bp[i][j]=(p[j-1]==s[i-1]) && bp[i-1][j-1]

    如果p[j]是?,则p[j]匹配任意一个字符,bp[i][j]=bp[i-1][j-1]

    如果p[j]是*,如果*代表0个字符的话,则bp[i][j]=b[i][j-1],如果*代表多个字符的话,则s的前i个字符和p的前j个字符是否匹配,取决于s的前i-1个字符和p的前j个字符是否匹配。如果b[i-1][j]=true,则b[i][j]=true,此时即*代表的字符序列增加了一个字符s[i]而已。所以bp[i][j]=bp[i-1][j] || bp[i][j-1]

    求解代码:(其实核心代码就几行,剩下的都是一些分配数组内存、释放内存、初始化之类的东西)

    #include<bits/stdc++.h>
    using namespace std;
    
    class Solution {
    public:
    	bool **bp;
    	//bp[i][j]:whether the first i characters of s and the first j characters of p match
        bool isMatch(string s, string p) {
    		if(s.size()==0){
    			if(p.size()!=0){
    				for(int i=0;i<p.size();++i){
    					if(p[i]!='*') return false;
    				}
    				return true;
    			}else{
    				return true;
    			}
    		}else if(p.size()==0) return false;
    		
    		//cout<<"s="<<s<<"  p="<<p<<endl;
    		
            init(s.size(),p.size());
    		
    		//edge value
    		bp[0][0]=true;
    		unsigned int tmp=1;
    		for(;tmp<=p.size();++tmp){
    			if(p[tmp-1]!='*') break;
    			bp[0][tmp]=true;
    		}
    		for(;tmp<=p.size();++tmp) bp[0][tmp]=false;
    		
    		for(unsigned int i=1;i<=s.size();++i){
    			for(unsigned int j=1;j<=p.size();++j){
    				if(p[j-1]=='?') bp[i][j]=bp[i-1][j-1];
    				else if(p[j-1]!='*') bp[i][j]=(p[j-1]==s[i-1]) && bp[i-1][j-1];
    				else bp[i][j]=bp[i-1][j] || bp[i][j-1];
    			}
    		}
    		
    		bool ret=bp[s.size()][p.size()];
    		
    		//cout<<"3 bp="<<endl;
    		//for(unsigned int i=0;i<=s.size();++i){
    			//for(unsigned int j=0;j<=p.size();++j){
    				//cout<<bp[i][j]<<" ";
    			//}
    			//cout<<endl;
    		//}
    		
    		//cout<<"ret="<<ret<<endl;
    		finish(s.size());
    		return ret;
        }
    	void init(unsigned int s_size,unsigned int p_size);
    	void finish(unsigned int s_size);
    };
    
    void Solution::finish(unsigned int s_size){
    	for(unsigned int i=0;i<=s_size;++i) delete []bp[i];
    	delete []bp;
    }
    
    void Solution::init(unsigned int s_size,unsigned int p_size){
    	bp=new bool*[s_size+1];
    	for(unsigned int i=0;i<=s_size;++i){
    		bp[i]=new bool[p_size+1];
    	}
    	for(unsigned int i=0;i<=s_size;++i){
    		for(unsigned int j=0;j<=p_size;++j) bp[i][j]=false;
    	}
    }

    后来在网上看到一篇线性时间复杂度的解法。但是这种解法我觉得属于trick的解法了,不具备通用性。不管怎样也先记录下来吧:

    我们以s="abcdcdef"   p="ab*cdef"为例来说明

    设i1为s的下标指针,i2为p的下标指针,初始i1=i2=0

    1、s[i1]=p[i2],所以++i1,++i2

    2、p[i2]=*,所以ss=i1,star=i2(star记录星号的位置,s[0]~s[ss]和p[0]~p[star]匹配,此时star所在的星号代表0个字符),i2=star+1,  ++i1(继续判断i1和i2是否匹配)

    3、s[i1]=p[i2],所以++i1,++i2

    4、s[i1]=p[i2],所以++i1,++i2

    5、s[i1]和p[i2]不匹配,所以当star位置的星号代表0个字符的时候无法匹配,所以下一步尝试star位置的星号代表一个字符。++ss,i1=ss+1,i2=star+1

    6、s[i1]和p[i2]不匹配,所以当star位置的星号代表一个字符的时候也无法匹配,所以下一步尝试star位置的星号代表两个字符。++ss,i1=ss+1,i2=star+1。此时匹配。

    大致就是这个思路,我根据这个求解的思路写的程序:

    #include<bits/stdc++.h>
    using namespace std;
    
    class Solution {
    public:
        bool isMatch(string s, string p) {
    		unsigned int ss=0;
    		int star=-1;
    		unsigned int i1=0,i2=0;
    		while(i1<s.size()){
    			
    			if(i2<p.size() && (p[i2]==s[i1]||p[i2]=='?')){
    				++i1;
    				++i2;
    				continue;
    			}
    			
    			if(i2<p.size() && p[i2]=='*'){
    				ss=i1-1;
    				star=i2++;
    				continue;
    			}
    			
    			if(star!=-1){
    				i2=star+1;
    				++ss;
    				i1=ss+1;
    			}else{
    				return false;
    			}
    		}
    		//cout<<"i1="<<i1<<"  i2="<<i2<<endl;
    		for(;i2<p.size() && p[i2]=='*';++i2);
    		return i2==p.size()?true:false;
        }
    };
    

     

    展开全文
  • The matching wildcard is strict, but no declaration can be found for element 'dubbo:application'. 在xml里经常会报错,查看错误信息会像类似的报错, 原因是:在配置文件里用的是标签,程序不知道你的...

    The matching wildcard is strict, but no declaration can be found for element 'dubbo:application'.


    在xml里经常会报错,查看错误信息会像类似的报错,

    原因是:在配置文件里用的是标签,程序不知道你的标签表示什么意思。

    比如我这里没有定义  <dubbo:application /> 。

    wildcard:通配符


    解决方法:

    在你的配置文件头部会有一个.xsd的网址,我这里是:http://code.alibabatech.com/schema/dubbo/dubbo.xsd

    window --> preferences --> 在左上方输入框输入  “xml c,会在下面看到  xml catalog --> 右边点击 user specified entried --> 右边添加



    展开全文
  • 44. Wildcard Matching

    2019-04-02 04:07:55
    44. Wildcard Matching方法1: dynamic programmingComplexity Given an input string (s) and a pattern §, implement wildcard pattern matching with support for ‘?’ and ‘*’. ‘?’ Matches any single ...


    Given an input string (s) and a pattern §, 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).

    Note:

    s could be empty and contains only lowercase letters a-z.
    p could be empty and contains only lowercase letters a-z, and characters like ? or *.
    Example 1:

    Input:
    s = "aa"
    p = "a"
    Output: false
    Explanation: "a" does not match the entire string "aa".
    

    Example 2:

    Input:
    s = "aa"
    p = "*"
    Output: true
    Explanation: '*' matches any sequence.
    

    Example 3:

    Input:
    s = "cb"
    p = "?a"
    Output: false
    Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
    

    Example 4:

    Input:
    s = "adceb"
    p = "*a*b"
    Output: true
    Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
    

    Example 5:

    Input:
    s = "acdcb"
    p = "a*c?b"
    Output: false
    

    方法1: dynamic programming

    Tushar: https://www.youtube.com/watch?v=3ZDZ-N0EPV0
    思路:

    用一个dp(m + 1, n + 1)大小的bool数组来表示, dp[i][j]记录以s[i - 1]为结尾和以p[j - 1]为结尾的字符串是否match。

    初始化:第一行表示,当s = “”, p是否能match。此时只有两种情况为true:1. p也为“”,2. p只有一个‘*’。第一列表示,当p = “”,p是否能match s。只有s = “” 为true。
    转移方程:

    1. 当p[j - 1] == ‘?’ ,继承dp[i][j] =dp[i - 1][j - 1]
    2. 当p[j - 1] == s[i - 1], 继承dp[i][j] =dp[i - 1][j - 1]
    3. 当p[j -1] == ‘*’ :
      3.1 ‘ * ’表示了空字符串,继承 dp[i - 1][j]
      3.2 ’ * '包括了s[i - 1]位,继承dp[i][j - 1]
      返回:dp[m][n]

    Complexity

    Time complexity: O(mn)
    Space complexity: O(mn)

    class Solution {
    public:
        bool isMatch(string s, string p) {
            int m = s.size();
            int n = p.size();
            
            vector<vector<int>> dp(m + 1, vector<int> (n + 1, false));
            dp[0][0] = true;
            
            // 如果p为一个或一连串的星号,可以和s = “”匹配
            for (int j = 1; j < n + 1; j++){
                if (p[j - 1] == '*') dp[0][j] = dp[0][j - 1];
            }
            
            for (int i = 1; i < m + 1; i++){
                for (int j = 1; j < n + 1; j ++){
                    if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                    else if (p[j - 1] == '*') {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                    }
                    else {
                        dp[i][j] = false;
                    }
                }
            }
            return dp[m][n];
        }
    };
    
    展开全文
  • 觉得Wildcard Matching & Regular Expression Matching & KMP都是字符串匹配问题,所以想把它们放一起 方法有动态规划、回溯、有限自动机 一、Wildcard Matching: Implement wildcard pattern matching with ...
  • 搭建dubbo服务时提示无法下载dubbo.xsd文件,可能因为xml引用的网站地址找不当前使用dubbo版本。... - cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration can be f...
  • Wildcard Matching Iteration

    2015-07-11 21:47:43
    思路: 方法一:递归。TLE。 方法二:迭代。
  • Problem 10 Regular Expression Matching 参考 https://blog.csdn.net/hk2291976/article/details/51165010 这道正则表达式匹配的问题,直接查的博客,看到一篇思路比较好的,包括回溯和动态规划两种方法 补充...
  • *LeetCode Wildcard Matching

    2016-01-10 00:10:43
    https://leetcode.com/problems/wildcard-matching/ 方法一:DFS (需要开数组判重) 这里我得承认,作弊了点,,因为有一组数据,长度4100左右两个字符串匹配。 所以开数组大小其实是WA了一次 然后才确定大小的...
  • 解决方法: 需要在 namespace 后加上对应的 schemaLocation,如下所示: <?xml version="1.0" encoding="UTF-8"?> <beans xmlns="http://www.springframework.org/schema/beans" xm...
  • Wildcard Matching@LeetCode

    2015-04-03 18:27:36
    Wildcard Matching 一开始是非常想用递归的方法做的,因为前面已经有做正则表达式的经验了,所以认为这一题应该是同样的思路做。但是小数据集还好,大数据集根本过不去,分析了一下,主要是要回朔的地方太多了,...
  • Wildcard Matching '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). Th
  • Wildcard Matching -- LeetCode

    万次阅读 多人点赞 2014-03-19 00:24:10
    原题链接: http://oj.leetcode.com/problems/wildcard-matching/  这道题目其实是Regular Expression Matching的简化版,在这里'?'相当于那边的'.',而'*'相当于那边的'.*',因为这里'*'就可以代替任何字符串,不...
  • 44. Wildcard Matching(通配符匹配) Wildcard Matching通配符匹配 题目链接 题目描述 题目分析 方法BFS 算法描述 参考代码 题目链接 ...
  • The matching wildcard is strict, but no declaration can be found for element 'aop:config'. applicationContext.xml /BookManageSystem/src/main/resources line 126 XML Problem 这是错误名 解决方法:...
  •  今天重装了一下MyEclipse7.5,打开原来的Flex项目,又报了以下两个错误,之前解决过,但不想又出现,于是把它的解决方法贴出来,做个备忘!...cvc-complex-type.2.4.c: The matching wildcard is strict, b...
  • xml文件中context:property-placeholder标签报错:“The matching wildcard is strict, but no declaration can be found for element 'context:prop” 解决方法,添加"xmlns:context=...
  • LeetCode之Wildcard Matching

    2015-07-06 21:39:52
    /*这里的难度主要是理解题意,题中要点如下: 1.字符‘?’能匹配任何单个字符;...根据以上题意,遍历p中*所有的匹配情况,即可获得解答方法。*/ class Solution { public: bool isMatch(string s, string p) {
  • 方法1: recursion + memo。 class Solution { Map<Pair<Integer, Integer>, Boolean> map = new HashMap<>(); public boolean isMatch(String s, String p) { return dfs(s, p, 0, 0); } ...
  • cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration can be found for element解决方法
  • Wildcard Matching题目: 这种题首先应该确定是用DP方法做。但是这题比[10题]简单一些。因为这里`*`可以匹配任意长度。所以对于`*`只要判断同一行的上列位置或者同一列的上一行位置是否为真就好。而?只要判
  •  今天重装了一下MyEclipse7.5,打开原来的Flex项目,又报了以下两个错误,之前解决过,但不想又出现,于是把它的解决方法贴出来,做个备忘!...cvc-complex-type.2.4.c: The matching wildcard is stric
  • 编程题,通配符匹配(Wildcard Matching)与正则表达式匹配(Regular Expression Matching)解题方法讲解。
  • 今天重装了一下MyEclipse7.5,打开原来的Flex项目,又报了以下两个错误,之前解决过,但不想又出现...cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration can be found for element 'flex:
  • 报错的原因: ... 解决:找到你引入的dubbo的jar包,然后解压,找到dubbo.xsd进行本地引用就可以了,但是,引用的时候一定要注意,你引用的这个xsl里必须有你报错的规范,比如说你的标签dubbo:service报错,那么拟...

空空如也

空空如也

1 2 3 4
收藏数 78
精华内容 31
关键字:

matching方法wildcard