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;
}
}
這道題目是看了答案后寫出來的。
看了答案后感覺思路很清晰剪验，很簡潔肴焊。這才算是上乘的解法吧。
從頂層看功戚，他是按照 * 分成一個(gè)個(gè)塊娶眷。當(dāng)一個(gè)塊匹配完了，進(jìn)入下一個(gè)模塊啸臀。什么時(shí)候匹配完届宠？ ---> 當(dāng)碰到下一個(gè) * 時(shí)。
雙指針。當(dāng)碰到正規(guī)字符或者 ? 時(shí)豌注，都是正常的往前移動(dòng)伤塌。
當(dāng)碰到 *時(shí)，記錄下此刻的位置幌羞，已經(jīng) s 處的位置寸谜。然后用下一位和s原位置進(jìn)行匹配。
這是第一種情況属桦，即 * -> empty
然后雙指針移動(dòng)熊痴，然后突然又不匹配了。
于是 pp 再次回到 star + 1, ss 回到 match(此時(shí) match 本身 + 1)
此刻聂宾， * 表示一個(gè)字母果善。
然后雙指針繼續(xù)移動(dòng)，失敗了系谐，再退回來巾陕。然后 * 表示兩個(gè)字母，繼續(xù)纪他。
直到鄙煤， ss 走到頭，或者 pp走到下一個(gè) * ,然后茶袒，這個(gè) * 的任務(wù)就完成了梯刚，我們通過了這層模塊的比較。
當(dāng) ss到頭時(shí)薪寓，判斷 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
初始狀態(tài)：
dp[s.length() + 1][p.length() + 1]
dp[i][j] 表示 s 中前i個(gè)字母 與 p 中前j個(gè)字母是否match
唯一需要認(rèn)真考慮的是 *
如果
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個(gè)字母與p的前j個(gè)字母match母谎，然后 * 用來表示 s.charAt(i - 1), 那么是可以match的
如果 dp[i][j - 1] == true, 即瘦黑， s的前i個(gè)字母與p的前 j - 1個(gè)字母match，然后用 * 來表示 empty, 那么也是可以match的奇唤。
如果 dp[i - 1][j] == true, 即供璧， s的前i - 1 個(gè)字母與p的前j個(gè)字母match，并且p的第j個(gè)字母是 冻记，那么睡毒，用一起把s.charAt(i - 1)也表示了，即冗栗， * 表示不止一個(gè)的字母演顾，那么也是可以match的供搀。
這就是遞推式。然后就可以DP了钠至。
好久沒做DP了葛虐。 這道題目很像 edit distance 等題目。現(xiàn)在開始做棉钧。
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
