LintCode 通配符匹配分析

判断两个可能包含通配符“?”和“*”的字符串是否匹配。匹配规则如下:

'?' 可以匹配任何单个字符。 '*' 可以匹配任意字符串(包括空字符串)。

两个串完全匹配才算匹配成功。

函数接口如下: bool isMatch(const char *s, const char *p)

样例 一些例子:

isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "") → true isMatch("aa", "a") → true isMatch("ab", "?") → true isMatch("aab", "ca*b") → false

分析

方法一:

动态规划: match[i][j] : 表示从i到s.length,从j到p.length的是否匹配 状态转移方程: 如果 s[i]==p[j], 那么自然,match[i][j] = match[i+1][j+1]; 如果 p[j] == '?' 自然,match[i][j] = match[i+1][j+1]; 如果p[j] == '' 分三种情况, 只匹配s[i] 那么,match[i][j] = [i+1][j+1]; *作为空值出现 那么,macth[i][j] = match[i][j+1] *匹配两个或者以上字符 那么,match[i][j] = match[i+1][j]

初始化: 如果p的后面有连续字符为*时,可以初始化为true。

public class Solution {
    /**
     * @param s: A string 
     * @param p: A string includes "?" and "*"
     * @return: A boolean
     */
    public boolean isMatch(String s, String p) {
       boolean[][] match=new boolean[s.length()+1][p.length()+1];
        match[s.length()][p.length()]=true;
        
        
        
        for(int i=p.length()-1;i>=0;i--){
            if(p.charAt(i)!='*')
                break;
            else
                match[s.length()][i]=true;
        }
        for(int i=s.length()-1;i>=0;i--){
            for(int j=p.length()-1;j>=0;j--){
                if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?')
                        match[i][j]=match[i+1][j+1];
                else if(p.charAt(j)=='*')
                        match[i][j]=match[i+1][j]||match[i][j+1] || match[i+1][j+1];
                else
                    match[i][j]=false;
            }
        }
        return match[0][0];
     }
}

/*aab  s 

a**b   p

m[i][j]  

m[2][3] = m[3][4]
m[2][2] = if * == b:m[3][3]
            if * == empty m[2][3]
            if * == 其他 m[3][2]
            
*/

方法二

两根指针遍历,记录*出现的位置

public class WildcardMatching {
    public boolean isMatch(String str, String pattern) {
           int s = 0;
           int p = 0;
           int sMatch = -1;//*匹配s中的字符的终止位置
           int starIdx = -1;//最近一个*出现的位置
           while (s < str.length()){
                // advancing both pointers
                if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
                    s++;
                    p++;
                }
                // * found, only advancing pattern pointer,,先让* 作为empty出现,所以s不需要++
                else if (p < pattern.length() && pattern.charAt(p) == '*'){
                    starIdx = p;//record the index of *
                    sMatch = s;//record the * 匹配的s中的位置
                    p++;
                }
               //last pattern pointer was *, advancing string pointer,用*去匹配当前的串
                else if (starIdx != -1){
                    p = starIdx + 1;//只能用* 去匹配,所以p要回到*后面一个元素开始判断
                    sMatch++;//被*匹配了
                    s = sMatch;
                }
               //current pattern pointer is not star, last patter pointer was not *
              //characters do not match
                else return false;
            }
            
            //check for remaining characters in pattern
            while (p < pattern.length() && pattern.charAt(p) == '*')
                p++;
            
            return p == pattern.length();
         }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python研发

go基础编程 day-2

  零值并不等于空值,而是当变量声明为某种来兴后的默认零值,通常情况下默认值为0,bool为false,string为空字符串。

1092
来自专栏闻道于事

Java之分支和循环

Java中的分支语句: if语句: if语句的四种写法:   (1)   if(表达式_布尔值) {   ...   }   (2)   if(表达式_布...

3089
来自专栏码云1024

c++类的声明

2864
来自专栏noteless

[三]基础数据类型之Integer详解

2133
来自专栏专注研发

希尔排序(shell‘ sort)

希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序

1003
来自专栏ml

c语言格式大整理

1、C语言中,非零值为真,真用1表示;零值为假,假用0表示。 2、转义字符参考: \a 蜂鸣,响铃  \b 回退:向后退一格 ...

5297
来自专栏一个会写诗的程序员的博客

第2章 Kotlin 语法基础第2章 Kotlin 语法基础

人与人之间通过语言来交流沟通,互相协作。人与计算机之间怎样“交流沟通”呢?答案是编程语言。一门语言有词、短语、句子、文章等,对应到编程语言中就是关键字、标识符、...

1492
来自专栏老九学堂

【必读】C语言基础知识大全

C语言程序的结构认识 用一个简单的c程序例子,介绍c语言的基本构成、格式、以及良好的书写风格,使小伙伴对c语言有个初步认识。 例1:计算两个整数之和的c程...

5558
来自专栏Golang语言社区

Go 语言数据类型

在 Go 编程语言中,数据类型用于声明函数和变量。 数据类型的出现是为了把数据分成所需内存大小不同的数据,编程的时候需要用大数据的时候才需要申请大内存,就可以充...

3197
来自专栏老九学堂

【必读】超全的C语言基础知识大全

我们用一个简单的c程序例子,介绍c语言的基本构成、格式、以及良好的书写风格,加深小伙伴们对C语言的认识。

2302

扫码关注云+社区

领取腾讯云代金券