/*
* 10. Regular Expression Matching
QuestionEditorial Solution My Submissions
Total Accepted: 86843
Total Submissions: 387233
Difficulty: Hard
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
Hide Company Tags Google Uber Airbnb Facebook Twitter
Hide Tags Dynamic Programming Backtracking String
Hide Similar Problems (H) Wildcard Matching
*/
package dp;
public class RegularExpressMatch {
public boolean isMatch(String s, String p) {
// 參考視頻 https://www.youtube.com/watch?v=l3hda49XcDE
int M = s.length(), N = p.length();
boolean[][] T = new boolean[M + 1][N + 1];
T[0][0] = true;
char[] pattern = p.toCharArray();
char[] str = s.toCharArray();
// deal with patterns like a*, a*b, a*b*c
for (int j = 1; j < T[0].length; j++) {
if (pattern[j - 1] == '*') {
T[0][j] = T[0][j - 2];
}
}
for (int i = 1; i < T.length; i++) {
for (int j = 1; j < T[0].length; j++) {
if (pattern[j - 1] == '.' || str[i - 1] == pattern[j - 1]) {
T[i][j] = T[i - 1][j - 1];
} else if (pattern[j - 1] == '*') {
T[i][j] = T[i][j - 2];
if (pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1]) {
T[i][j] = T[i][j] | T[i - 1][j];
}
} else {
T[i][j] = false;
}
}
}
return T[M][N];
}
public static void main(String[] args) {
RegularExpressMatch rem = new RegularExpressMatch();
String str = "aab", pattern = "c*a*b";
System.out.println(rem.isMatch(str, pattern)); // true
}
}
10. Regular Expression Matching?
最后編輯于 ：
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門秆吵，熙熙樓的掌柜王于貴愁眉苦臉地迎上來失球，“玉大人，你說我怎么就攤上這事帮毁。” “怎么了豺撑？”我有些...
- 文/不壞的土叔 我叫張陵烈疚，是天一觀的道長。 經(jīng)常有香客問我聪轿，道長爷肝，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任陆错，我火速辦了婚禮灯抛，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘音瓷。我一直安慰自己对嚼，他們只是感情好，可當我...
- 文/花漫 我一把揭開白布绳慎。 她就那樣靜靜地躺著纵竖，像睡著了一般。 火紅的嫁衣襯著肌膚如雪杏愤。 梳的紋絲不亂的頭發(fā)上靡砌，一...
- 文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼骗炉！你這毒婦竟也來了照宝？” 一聲冷哼從身側(cè)響起，我...
- 正文 年R本政府宣布漫拭，位于F島的核電站，受9級特大地震影響混稽，放射性物質(zhì)發(fā)生泄漏采驻。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一匈勋、第九天 我趴在偏房一處隱蔽的房頂上張望礼旅。 院中可真熱鬧，春花似錦洽洁、人聲如沸痘系。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽碎浇。三九已至，卻和暖如春璃俗，著一層夾襖步出監(jiān)牢的瞬間奴璃，已是汗流浹背。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- Implement regular expression matching with support for '....
- 各位看官別怪我少見多怪攒盈，連這么經(jīng)典的題目都要拿出來說一遍抵拘。但是對于字符串和DP同時相關的題目我是真不熟練。型豁。僵蛛。這不...
- Implement regular expression matching with support for '....
- 題設 要點 二維數(shù)組動態(tài)規(guī)劃DP[][] 首先，按照之前解回文串的思路迎变，這種題可以考慮采用動態(tài)規(guī)劃的方法來做充尉。我們...
- Implement regular expression matching with support for '....
