[LintCode/LeetCode] Wildcard Matching
文章目录
Problem
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).
Example
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
Note
递归和动规的方法没有研究,说一下较为直观的贪心算法。
用cs和cp两个指针分别标记s和p进行比较的位置,当cs遍历完s后,若cp也遍历完p,说明完全配对。
我们看一下while循环里的几个分支:
第一个if语句,若cp和cs指向的字符相等,或cp指向的字符为'?',则说明这一位配对成功,两个指针继续前移;
第二个else if语句,当cp指向的字符为'*',则后面字符的配对结果要受到影响,必须用star和match分别在p和s的当前位置,也就是cp和cs,进行标记。然后,cp前移,cs不动,为什么呢?因为,如果此时cp == p.length(),就已经可以结束while循环了;但若cp不是末位,那么p剩下的字符还要继续判断,至于cs,完全可以等到下一次成功配对字符后再移动;
第三个else if语句,这里最为费解。当p之前出现过star,且此时cp和cs完全无法配对的时候,就一起退回在star和match配对过的位置。再将cp和cs逐个加1继续比较,并将match后移。为什么star不用后移呢?因为star是大BOSS,可以任意和后面match走过的很多位配对下去呀;
最后一个else语句,返回false。但是这个false包含了哪些情况呢?其实,就是p中没有star且无法配对的情况。
再用一个while循环跳过p尾部的所有'*',如果有的话。
最后,若cp走完p,说明完全配对。
Solution
Greedy
public class Solution {
public boolean isMatch(String s, String p) {
int cs = 0, cp = 0, star = -1, match = 0;
while (cs < s.length()) {
if (cp < p.length() && (p.charAt(cp) == s.charAt(cs) || p.charAt(cp) == '?')) {
cs++;
cp++;
}
else if (cp < p.length() && p.charAt(cp) == '*') {
star = cp;
match = cs;
cp++;
}
else if (star != -1) {
cp = star + 1;
cs = match + 1;
match++;
}
else return false;
}
while (cp < p.length() && p.charAt(cp) == '*') cp++;
return cp == p.length();
}
}
DP
public class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) return false;
int lens = s.length();
int lenp = p.length();
boolean[][] dp = new boolean[lens + 1][lenp + 1];
boolean flag = false;
for (int i = 0; i <= lens; i++) {
flag = false;
for (int j = 0; j <= lenp; j++) {
if (i == 0 && j == 0) {
dp[i][j] = true;
flag = true;
continue;
}
if (j == 0) {
dp[i][j] = false;
continue;
}
if (i == 0) dp[i][j] = dp[i][j - 1] && p.charAt(j - 1) == '*';
else dp[i][j] = (matchChar(s.charAt(i - 1), p.charAt(j - 1)) && dp[i - 1][j - 1])
|| (p.charAt(j - 1) == '*' && (dp[i][j - 1] || dp[i - 1][j]));
if (dp[i][j]) flag = true;
if (dp[i][j] && p.charAt(j - 1) == '*' && j == lenp) return true;
}
if (!flag) return false;
}
return dp[lens][lenp];
}
public static boolean matchChar(char c, char p) {
return (p == '?' || p == c);
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论