資訊專欄INFORMATION COLUMN
摘要：難度這道題要求我們實現(xiàn)簡單的正則表達式的匹配只要求普通字符的匹配了解正則的同學(xué)都清楚代表任意單個字符代表個或多個前面的字符比如可以匹配到空字符串也可以匹配等等題目還要求我們判定正則是否匹配給定的字符串要判定整個字符串而不是其中一部分匹配就算
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).
The function prototype should be: bool isMatch(const char *s, const
char *p)Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
難度: Hard
這道題要求我們實現(xiàn)簡單的正則表達式的匹配, 只要求普通字符 . *的匹配, 了解正則的同學(xué)都清楚, .代表任意單個字符, *代表0個或多個前面的字符, 比如a*可以匹配到空字符串, 也可以匹配 a, aaa等等. 題目還要求, 我們判定正則是否匹配給定的字符串, 要判定整個字符串, 而不是其中一部分匹配就算ok.
這是個典型的動態(tài)規(guī)劃的題, 作者在leetcode出來之前幾乎不做算法, 本著死磕到底不看答案不看別人解答的精神, 我嘗試了不止一種解法, 這里貼出兩個AC的解法.
任意確定字符, 必須精確匹配, . 匹配一個任意字符, 這些都很好判定, 關(guān)鍵在于, * 到底匹配多少個字符? 這就不好判定了, 只能根據(jù)一定規(guī)則去嘗試, 這里就是用到動態(tài)規(guī)劃的地方.
第一個AC的解法主要思路為:
切分正則的pattern, 將帶*號的都切開, 比如.aa* 可以切為 .~a~a* 三段
使用一個棧, 對不同的可能性(這些可能性實際上形成一個搜索樹)做深度優(yōu)先搜索(也可以不用棧, 直接遞歸, 我的代碼里沒有展示)
對于不帶*的分段, 直接嚴格匹配
對于帶*的分段, 如果跟當(dāng)前游標(biāo)處的字符相同, 則嘗試匹配一個字符(下次判定還可以匹配一個, 這樣實際可以做到匹配多個), 或者匹配0個(也就是將當(dāng)前子pattern分段拋棄); 如果跟當(dāng)前游標(biāo)處的字符不同, 則只能匹配0個, 將當(dāng)前子pattern分段拋棄.
代碼如下
public class Solution2 {
public class Symbol {
public Symbol() {
rep = false;
}
public Symbol(char f, boolean s) {
c = f;
rep = s;
}
public char c;
public boolean rep;
}
public class Pair {
public T first;
public T second;
public Pair() {
first = null;
second = null;
}
public Pair(T _f, T _s) {
first = _f;
second = _s;
}
}
/**
* AC, but slow
*/
public boolean isMatch(String s, String p) {
// parse pattern
List pl = new ArrayList();
int i = 0;
while (i < p.length()) {
char c;
boolean rep = false;
char a = p.charAt(i);
if (a != "*") {
c = a;
} else {
// regex wrong
return false;
}
i++;
if (i < p.length() && p.charAt(i) == "*") {
rep = true;
i++;
}
pl.add(new Symbol(c, rep));
}
// do match
Stack> q = new Stack>();
q.push(new Pair(0, 0));
while (!q.isEmpty()) {
Pair pr = q.pop();
if (isMatch(s, pr.first, pl, pr.second, q)) {
return true;
}
}
return false;
}
private boolean isMatch(String s, int sPos, List pl, int pPos, Stack> q) {
while (sPos < s.length() && pPos < pl.size()) {
Symbol sym = pl.get(pPos);
if (sym.rep) {
if (sym.c == "." || sym.c == s.charAt(sPos)) {
q.push(new Pair(sPos, pPos + 1));
q.push(new Pair(sPos + 1, pPos));
} else {
q.push(new Pair(sPos, pPos + 1));
}
return false;
} else {
if (sym.c != s.charAt(sPos) && sym.c != ".") {
return false;
}
}
sPos++;
pPos++;
}
if (sPos < s.length()) {
return false;
}
if (pPos < pl.size()) {
while (pPos < pl.size()) {
if (!pl.get(pPos).rep) {
return false;
}
pPos++;
}
}
return true;
}
public static void main(String[] args) {
Solution2 s = new Solution2();
System.out.println(s.isMatch("aa", "a"));
System.out.println(s.isMatch("aa", "aa"));
System.out.println(s.isMatch("aaa", "aa"));
System.out.println(s.isMatch("aa", "a*"));
System.out.println(s.isMatch("aa", ".*"));
System.out.println(s.isMatch("aab", "c*a*b"));
System.out.println(s.isMatch("ab", ".*"));
System.out.println(s.isMatch("aaab", ".*ab"));
System.out.println(s.isMatch("aaa", "a*a"));
System.out.println(s.isMatch("aaa", "aaab*"));
System.out.println(s.isMatch("bbab", "b*"));
System.out.println(s.isMatch("bbab", "a*"));
System.out.println(s.isMatch("bbab", "b*a*"));
System.out.println(s.isMatch("bbab", "...."));
System.out.println(s.isMatch("abbabaaaaaaacaa", "a*.*b.a.*c*b*a*c*"));
System.out.println(s.isMatch("bbabaaaaaaacaa", "b.a.*c*b*a*c*"));
System.out.println(s.isMatch("baaaaaaacaa", ".*c*b*a*c*"));
System.out.println(s.isMatch("caa", "c*b*a*c*"));
System.out.println(s.isMatch("caa", "c*b*a*"));
System.out.println(s.isMatch("a", "a*b*"));
System.out.println(s.isMatch("a", "a*.*"));
System.out.println(s.isMatch("ab", "a*b"));
System.out.println(s.isMatch("b", ".*b"));
System.out.println(s.isMatch("ab", ".*b"));
System.out.println(s.isMatch("aaaaaaaaaaaaab", "a*a*a*a*a*a*a*a*a*a*a*a*b"));
}
}
main中包含了測試用例.
這個解法雖然AC了, 但是存在以下問題:
執(zhí)行速度較慢, 只超過了百分之幾的成功提交.(直接改遞歸在java中會更快的)
代碼思路不是很清晰
這種動態(tài)規(guī)劃比較保守, 判定較長, 搜索的樹比較深.
于是嘗試了第二個解法, 跟第一個很不同, 主要思路為:
首先還是切分正則的pattern, 將帶*號的都切開, 比如.aa* 可以切為 .~a~a* 三段. 不過圖方便直接切成多個string即可, 其實也有其他的存儲方案.
從前/后兩個方向, 遍歷子pattern列表, 把不重復(fù)(不帶*)的部分, 跟目標(biāo)字符串的相應(yīng)位置做嚴格匹配, 直到遇到帶*的子pattern. 此時匹配不成功可以認為正則匹配失敗.
剩下的子pattern列表中, 如果包含不帶*號的子pattern, 則尋找所有在目標(biāo)字符串中能匹配到的字符, 對每個這樣的字符, 把字符串和子pattern列表切分成兩段, 看這兩段是否可以匹配, 當(dāng)且僅當(dāng)這兩段都匹配成功, 才算整個字符串匹配正則成功.
剩下的子pattern列表中, 如果不包含不帶*號的子pattern, 即全部都是帶*的模糊匹配. 我們就采用貪心算法, 對每個子pattern, 匹配盡量多的字符, 如果能把當(dāng)前字符串匹配干凈, 就算ok.
public class Solution3 {
/**
* AC, fast enough
*/
public boolean isMatch(String s, String p) {
List plist = new ArrayList();
int pi = 0;
while (pi < p.length()) {
if (p.charAt(pi) == "*") {
// regex wrong
return false;
}
if (pi + 1 < p.length() && p.charAt(pi + 1) == "*") {
plist.add(p.substring(pi, pi + 2));
pi += 2;
} else {
plist.add(p.substring(pi, pi + 1));
pi += 1;
}
}
return isMatch(s, 0, s.length(), plist, 0, plist.size());
}
/**
*
* @param s string to be matched
* @param ss start position of s (inclusive)
* @param se end position of s (exclusive)
* @param plist pattern list
* @param ps start position of plist (inclusive)
* @param pe end position of plist (exclusive)
* @return
*/
public boolean isMatch(String s, int ss, int se, List plist, int ps, int pe) {
if (ps == pe) {
if (ss != se) {
return false;
} else {
return true;
}
}
while (ps < pe && plist.get(ps).length() == 1 && ss < se) {
char c = plist.get(ps).charAt(0);
if (c != "." && c != s.charAt(ss)) {
return false;
}
ss++;
ps++;
}
while (ps < pe && plist.get(pe - 1).length() == 1 && ss < se) {
char c = plist.get(pe - 1).charAt(0);
if (c != "." && c != s.charAt(se - 1)) {
return false;
}
se--;
pe--;
}
if (ps == pe && ss == se) {
return true;
}
if (ps == pe) {
return false;
}
if (ss == se) {
for (int i = ps; i < pe; i++) {
if (plist.get(i).length() == 1) {
return false;
}
}
return true;
}
// select one single sub-pattern
int pi = 0;
for (pi = ps; pi < pe; pi++) {
if (plist.get(pi).length() == 1) {
break;
}
}
if (pi < pe) {
// found single sub-pattern
char c = plist.get(pi).charAt(0);
for (int si = ss; si < se; si++) {
if (c == "." || s.charAt(si) == c) {
boolean b1 = isMatch(s, ss, si, plist, ps, pi);
if (!b1) {
// early termination
continue;
}
boolean b2 = isMatch(s, si + 1, se, plist, pi + 1, pe);
if (b2) {
return true;
}
}
}
return false;
}
// single sub-pattern not found, all * patterns
// do greedy
for (pi = ps; pi < pe; pi++) {
char c = plist.get(pi).charAt(0);
if (c == ".") {
// will consume all
return true;
}
while (ss < se && (s.charAt(ss) == c)) {
ss++;
}
if (ss == se) {
return true;
}
}
return false;
}
public static void main(String[] args) {
Solution3 s = new Solution3();
System.out.println(s.isMatch("aa", "a"));
System.out.println(s.isMatch("aa", "aa"));
System.out.println(s.isMatch("aaa", "aa"));
System.out.println(s.isMatch("aa", "a*"));
System.out.println(s.isMatch("aa", ".*"));
System.out.println(s.isMatch("aab", "c*a*b"));
System.out.println(s.isMatch("ab", ".*"));
System.out.println(s.isMatch("aaab", ".*ab"));
System.out.println(s.isMatch("aaa", "a*a"));
System.out.println(s.isMatch("aaa", "aaab*"));
System.out.println(s.isMatch("bbab", "b*"));
System.out.println(s.isMatch("bbab", "a*"));
System.out.println(s.isMatch("bbab", "b*a*"));
System.out.println(s.isMatch("bbab", "...."));
System.out.println(s.isMatch("abbabaaaaaaacaa", "a*.*b.a.*c*b*a*c*"));
System.out.println(s.isMatch("bbabaaaaaaacaa", "b.a.*c*b*a*c*"));
System.out.println(s.isMatch("baaaaaaacaa", ".*c*b*a*c*"));
System.out.println(s.isMatch("caa", "c*b*a*c*"));
System.out.println(s.isMatch("caa", "c*b*a*"));
System.out.println(s.isMatch("a", "a*b*"));
System.out.println(s.isMatch("a", "a*.*"));
System.out.println(s.isMatch("ab", "a*b"));
System.out.println(s.isMatch("b", ".*b"));
System.out.println(s.isMatch("ab", ".*b"));
System.out.println(s.isMatch("aaaaaaaaaaaaab", "a*a*a*a*a*a*a*a*a*a*a*a*b"));
}
}
main中包含了測試用例.
這個解法看代碼直覺就可以感到搜索深度會相對于上個解法小很多, 因為能在本次判定中完成的, 就在本次判定中完成, 不放到下次. 實際也可以超過75%的提交, 并且思路相對清晰的多, 雖然代碼長了點.
可以看到, 對于動態(tài)規(guī)劃的問題, 需要做的是:
確定的部分盡快匹配, 給出答案
不確定的部分, 多帶帶切分出來, 使用動態(tài)規(guī)劃
以上是我的解法, 不知道是否有更好更清晰的解.
另: 這道題跟 Leetcode 44 通配符匹配很相似, 稍后給出Leetcode 44的解.
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/66509.html
摘要：為的條件是為，且第個字符也能被成功匹配。而從后往前匹配則不會影響該星號后面星號所匹配的部分，因為已經(jīng)匹配的部分我們會直接跳過。這樣才能防止最后字母沒有匹配上，而前面的部分反而把的結(jié)尾給匹配了。 Regular Expression Matching Implement regular expression matching with support for . and*. . Mat...
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. Th...
摘要：手動實現(xiàn)正則表達式匹配函數(shù)思路使用迭代，當(dāng)每次判斷后令當(dāng)時特殊處理，注意可以代表到多個之前一個的字符當(dāng)時，循環(huán)判斷代表多少個之前一個的字符，如果可以匹配之后的模式，返回，否則注意處理邊界值的情況，和為空串時代碼可以代表一到多次本題以及其它題 手動實現(xiàn).*正則表達式匹配函數(shù) regular expression matching . Matches any single charact...
摘要：題目鏈接這道題還是可以用的方法，用的數(shù)組來解，空間復(fù)雜度較高。和不同，這道題的符號和前面的沒有關(guān)系，不需要一起考慮。最壞的情況下，間隔出現(xiàn)且每個都要匹配很多字符，設(shè)一個平均匹配里面?zhèn)€字符，。其中，是的長度，是的長度。 Wildcard Matching 題目鏈接：https://leetcode.com/problems...這道題還是可以用Regular Expression Mat...
閱讀 2548·2023-04-25 19:47
閱讀 3389·2019-08-29 17:18
閱讀 858·2019-08-29 15:26
閱讀 3364·2019-08-29 14:17
閱讀 1129·2019-08-26 13:49
閱讀 3342·2019-08-26 13:22
閱讀 3027·2019-08-26 10:44
閱讀 2699·2019-08-23 16:51
