資訊專欄INFORMATION COLUMN
Problem
Given an input string (s) and a pattern (p), implement regular expression matching with support for "." and "*".
"." Matches any single character. "*" Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa" p = "a*" Output: true Explanation: "*" means zero or more of the precedeng element, "a". Therefore, by repeating "a" once, it becomes "aa".
Example 3:
Input: s = "ab" p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input: s = "aab" p = "c*a*b" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:
Input: s = "mississippi" p = "mis*is*p*." Output: falseSolution
class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) return false;
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;
for (int i = 1; i < p.length(); i++) {
if (p.charAt(i) == "*" && dp[0][i-1]) dp[0][i+1] = true;
}
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
// "." or same char
if (p.charAt(j) == "." || p.charAt(j) == s.charAt(i)) {
dp[i+1][j+1] = dp[i][j];
} else if (j != 0 && p.charAt(j) == "*") {
if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != ".") {
dp[i+1][j+1] = dp[i+1][j-1];
} else {
//multiple s.charAt(i) or none s.charAt(i)
dp[i+1][j+1] = dp[i][j+1] || dp[i+1][j-1];
}
}
}
}
return dp[s.length()][p.length()];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/71801.html
摘要：為的條件是為，且第個(gè)字符也能被成功匹配。而從后往前匹配則不會(huì)影響該星號(hào)后面星號(hào)所匹配的部分，因?yàn)橐呀?jīng)匹配的部分我們會(huì)直接跳過(guò)。這樣才能防止最后字母沒(méi)有匹配上，而前面的部分反而把的結(jié)尾給匹配了。 Regular Expression Matching Implement regular expression matching with support for . and*. . Mat...
摘要：難度這道題要求我們實(shí)現(xiàn)簡(jiǎn)單的正則表達(dá)式的匹配只要求普通字符的匹配了解正則的同學(xué)都清楚代表任意單個(gè)字符代表個(gè)或多個(gè)前面的字符比如可以匹配到空字符串也可以匹配等等題目還要求我們判定正則是否匹配給定的字符串要判定整個(gè)字符串而不是其中一部分匹配就算 Implement regular expression matching with support for . and *. . Matche...
摘要：解釋清楚這兩個(gè)條件是如何推導(dǎo)的。表示維持原位置，位置的，和位置的一同消失。 Implement regular expression matching with support for . and *. . Matches any single character. * Matches zero or more of the preceding element. The matchi...
摘要：題目鏈接這道題還是可以用的方法，用的數(shù)組來(lái)解，空間復(fù)雜度較高。和不同，這道題的符號(hào)和前面的沒(méi)有關(guān)系，不需要一起考慮。最壞的情況下，間隔出現(xiàn)且每個(gè)都要匹配很多字符，設(shè)一個(gè)平均匹配里面?zhèn)€字符，。其中，是的長(zhǎng)度，是的長(zhǎng)度。 Wildcard Matching 題目鏈接：https://leetcode.com/problems...這道題還是可以用Regular Expression Mat...
摘要：手動(dòng)實(shí)現(xiàn)正則表達(dá)式匹配函數(shù)思路使用迭代，當(dāng)每次判斷后令當(dāng)時(shí)特殊處理，注意可以代表到多個(gè)之前一個(gè)的字符當(dāng)時(shí)，循環(huán)判斷代表多少個(gè)之前一個(gè)的字符，如果可以匹配之后的模式，返回，否則注意處理邊界值的情況，和為空串時(shí)代碼可以代表一到多次本題以及其它題 手動(dòng)實(shí)現(xiàn).*正則表達(dá)式匹配函數(shù) regular expression matching . Matches any single charact...
閱讀 2965·2021-09-28 09:36
閱讀 3884·2021-09-27 13:59
閱讀 2634·2021-08-31 09:44
閱讀 2444·2019-08-30 15:54
閱讀 2421·2019-08-30 15:44
閱讀 1271·2019-08-30 13:45
閱讀 1313·2019-08-29 18:38
閱讀 1446·2019-08-29 18:37
