My code:
public class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
int ss = 0;
int pp = 0;
int star = - 1;
int match = -1;
while (ss < s.length()) {
if (pp < p.length() && p.charAt(pp) == '?') {
ss++;
pp++;
}
else if (pp < p.length() && p.charAt(pp) == s.charAt(ss)) {
ss++;
pp++;
}
else if (pp < p.length() && p.charAt(pp) == '*') {
star = pp;
match = ss;
pp++;
}
else if (star != -1) {
pp = star + 1;
match++;
ss = match;
}
else {
return false;
}
}
while (pp < p.length()) {
if (p.charAt(pp) != '*') {
return false;
}
pp++;
}
return true;
}
}
这道题目是看了答案后写出来的。
看了答案后感觉思路很清晰，很简洁。这才算是上乘的解法吧。
从顶层看，他是按照 * 分成一个个块。当一个块匹配完了，进入下一个模块。什么时候匹配完？ ---> 当碰到下一个 * 时。
双指针。当碰到正规字符或者 ? 时，都是正常的往前移动。
当碰到 *时，记录下此刻的位置，已经 s 处的位置。然后用下一位和s原位置进行匹配。
这是第一种情况，即 * -> empty
然后双指针移动，然后突然又不匹配了。
于是 pp 再次回到 star + 1, ss 回到 match(此时 match 本身 + 1)
此刻， * 表示一个字母。
然后双指针继续移动，失败了，再退回来。然后 * 表示两个字母，继续。
直到， ss 走到头，或者 pp走到下一个 * ,然后，这个 * 的任务就完成了，我们通过了这层模块的比较。
当 ss到头时，判断 pp 到头是否都是 *, 如果不是，就得返回 false
reference:
https://discuss.leetcode.com/topic/3040/linear-runtime-and-constant-space-solution
下面介绍 DP
My code:
public class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
int row = s.length() + 1;
int col = p.length() + 1;
boolean[][] dp = new boolean[row][col];
dp[0][0] = true;
for (int i = 1; i < col; i++) {
if (p.charAt(i - 1) == '*') {
dp[0][i] = dp[0][i - 1];
}
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (p.charAt(j - 1) != '*') {
if (p.charAt(j - 1) == '?' || p.charAt(j - 1) == s.charAt(i - 1)) {
if (dp[i - 1][j - 1]) {
dp[i][j] = true;
}
}
else {
dp[i][j] = false;
}
}
else {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i - 1][j - 1];
}
}
}
return dp[row - 1][col - 1];
}
}
reference:
http://buttercola.blogspot.com/2014/10/leetcode-wildcard-matching.html
初始状态：
dp[s.length() + 1][p.length() + 1]
dp[i][j] 表示 s 中前i个字母 与 p 中前j个字母是否match
唯一需要认真考虑的是 *
如果
p.charAt(j) != '*'
那么， 如果 dp[i - 1][j - 1] == true
并且
s.charAt(i) == p.charAt(j) or p.charAt(j) == '?'
那么，dp[i][j] = true;
如果
p.charAt(j) == '*'
那么，
如果 dp[i - 1][j - 1] == true, 即，s的前i个字母与p的前j个字母match，然后 * 用来表示 s.charAt(i - 1), 那么是可以match的
如果 dp[i][j - 1] == true, 即， s的前i个字母与p的前 j - 1个字母match，然后用 * 来表示 empty, 那么也是可以match的。
如果 dp[i - 1][j] == true, 即， s的前i - 1 个字母与p的前j个字母match，并且p的第j个字母是 ，那么，用一起把s.charAt(i - 1)也表示了，即， * 表示不止一个的字母，那么也是可以match的。
这就是递推式。然后就可以DP了。
好久没做DP了。 这道题目很像 edit distance 等题目。现在开始做。
Anyway, Good luck, Richardo! -- 08/1
My code:
iteration
public class Solution {
public boolean isMatch(String s, String p) {
int ss = 0;
int pp = 0;
int star = -1;
int match = -1;
while (ss < s.length()) {
if (pp < p.length() && (s.charAt(ss) == p.charAt(pp) || p.charAt(pp) == '?')) {
ss++;
pp++;
}
else if (pp < p.length() && p.charAt(pp) == '*') {
star = pp;
match = ss;
pp++;
}
else if (star != -1) {
pp = star + 1;
match++;
ss = match;
}
else {
return false;
}
}
for (int i = pp; i < p.length(); i++) {
if (p.charAt(i) != '*') {
return false;
}
}
return true;
}
}
DP:
My code:
public class Solution {
public boolean isMatch(String s, String p) {
if (p.length() == 0) {
return s.length() == 0;
}
else if (p.length() == 1) {
if (s.length() == 1 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) {
return true;
}
else {
return false;
}
}
else if (p.charAt(1) != '*') {
if (s.length() == 0) {
return false;
}
else if (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') {
return isMatch(s.substring(1), p.substring(1));
}
else {
return false;
}
}
else {
if (isMatch(s, p.substring(2))) {
return true;
}
while (s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) {
s = s.substring(1);
if (isMatch(s, p.substring(2))) {
return true;
}
}
return false;
}
}
}
看了下以前的答案，再写了下。
Anyway, Good luck, Richardo! -- 09/16/2016
