192. Wild card matching

Leave a comment

September 21, 2016 by oneOokay

晚饭捣了一瓣蒜做蒜泥料吃了,到现在还满口的蒜味。FML。以及ladder终于还剩最后一题了TOT

总的有两种解法,一种是用index来逐个判断来做。另一个是dp,dp可以简化为一维的dp,暂时还没看懂,以后再看吧。。。而且dp在这套题上比较容易超时好像。

方法一的总体思想是:假设s[i-1]匹配p[j-1],那么

  1. 当s[i] == p[j] 或者p[j] == ‘?’时,s[i]将会匹配p[j]
  2. 当p[j] == ‘*’的时候比较复杂。因为*匹配0至n个任意字符串。
    1. 继续j+1一直找到连续的*的之后的第一个字符串。
    2. 记录下此时p的index为preP,记录下此时s的index为preS,一个flag表示p中存在*为true
    3. 从此时p的index和此时s的index继续进行匹配
    4. 如果发现存在不匹配,那么把preS加1,s和p两个字符串从preS+1和preP开始重新匹配。此时相当于preS的那个字符被p中的*匹配掉了。如此进行循环。

网上称之为“贪心”/指针算法。这里的两个都还挺好的,但是要先看第一个,第二个是第一个的改善:http://www.cnblogs.com/yuzhangcmu/p/4116153.html 。这里也有点解释:https://simpleandstupid.com/2014/10/26/wildcard-matching-leetcode-%E8%A7%A3%E9%A2%98%E7%AC%94%E8%AE%B0/

public boolean isMatch(String s, String p) {
if (s == null && p == null) {
return true;
}
if (s == null || p == null) {
return false;
}
int indexS = 0;
int indexP = 0;
int lengthS = s.length();
int lengthP = p.length();
int preS = -1;
int preP = -1;

while (indexS < lengthS) {
if (indexP < lengthP && (p.charAt(indexP) == s.charAt(indexS) || p.charAt(indexP) == ‘?’)){
indexS ++;
indexP ++;
}else if (indexP < lengthP && p.charAt(indexP) == ‘*’) { //否则如果当p上的char为’*’的时候,由于’*’可以匹配0到任意字符(>=0)
while (indexP < lengthP && p.charAt(indexP) == ‘*’){ //这里由于一个*和多个*的效果是一样的,这里用来找到一连串的*里面的最后一个*
indexP ++; //p里出现在*之后的第一个字符
}
if (indexP == lengthP) {//while循环结束之一,p之后就一直都是*,一直到结尾。p从某个位置与s匹配成功,从这个位置之后的所有字符都是’*’,所以p和s是匹配的,不需要继续判断了,返回true
return true;
}
back = true;  //设置back flag 为true
preS = indexS; //记录当前S的index
preP = indexP; //记录当前P的index,为*之后的第一个
}else if (back){//如果以上if都不符合的话,说明目前字符串不匹配。但是因为back为true,说明前面存在*,于是我们把preS首先要加一,以便下一次的back,把这个值赋给indexS。注意indexP不变。再继续进行匹配。
indexS = ++ preS;
indexP = preP;
}else {//s和p字符不符,之前又没有*号的存在,所以不匹配,返回false;
return false;
}}

while (indexP < lengthP && p.charAt(indexP) == ‘*’){ //之前的while loop结束,indexS == S.length.此时如果P之后都是*的话,继续更新indexP。如果P之后不是*,那么最后的肯定是返回false的
indexP ++;
}

if (indexP == lengthP && indexS == lengthS) {//最终是:完成对s和p完整的字符串的判断了,两个字符串匹配,返回true。
return true;
}
return false;
}

解法二:

public boolean isMatch(String s, String p) {
if (s == null && p == null) {
return true;
}

if (s == null || p == null) {
return false;
}

int indexS = 0;
int indexP = 0;
int lengthS = s.length();
int lengthP = p.length();
int preS = -1;
int preP = -1;
while (indexS < lengthS) {
if (indexP < lengthP && (p.charAt(indexP) == s.charAt(indexS) || p.charAt(indexP) == ‘?’)){
indexS ++;
indexP ++;
}else if (indexP < lengthP && p.charAt(indexP) == ‘*’) {
preS = indexS;
preP = indexP;
indexP ++; //直接把对p的*的判断放入总的while循环中
}else if (preP != -1){ //用preP的index来代替之前的back boolean
preS ++;
indexS = preS;
indexP = preP + 1;
}else {
return false;
}}
while (indexP < lengthP){
if(p.charAt(indexP) != ‘*’){ 
return false;
}
indexP ++;
}
return true;
}

 

这题用dp做,参考看这里:http://www.cnblogs.com/yuzhangcmu/p/4116153.html

f[i][j]来表示,P从0到i的字符串能否匹配S从0到j的字符串。

先来考虑f[i][j]和f[i-1][j-1]的关系:f[i][j] = f[i-1][j-1] && (p.charAt(i) == s.charAt(j) || p.charAt(i) == ‘?’ || p.charAt(i) == ‘*’) f[i-1][j-1]match的话,只有当p在i点的字符与s在j的字符相等或者p在i的字符为?或者*。这里当p.charAt(i) == ‘*’ 特殊要单独拎出来考虑,因为*可以match 0 到多个字符

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: