由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 贡献个regular expression DP解法
相关主题
aababccbc remove abc讨论一道两个linked list的题目
求教一个string match 的 dp 解法专家们,find the longest common substring of two strings
问个题?两个Sorted Array,找K smallest element
这题谁知道答案?求一题的完美简洁解答
经典面试题重新看一道经典题
求教电面遇到的一道pattern match的实现问个MSFT的题
求两个程序的C++ code求教 合并两数组 并排除重复
airBnb电面面经做题做得很郁闷,求指点
相关话题的讨论汇总
话题: dp话题: result话题: int话题: pattern话题: len2
进入JobHunting版参与讨论
1 (共1页)
p*****3
发帖数: 488
1
//DP矩阵中如果遇到.*或.+, 那么DP[i][j] == DP[i][j+1] = true/false
const int M = 100;
bool isMatchDP(const char* str, const char* pattern)
{
if (NULL == str || NULL == pattern)
return false;
int len1 = strlen(str);
int len2 = strlen(pattern);
bool DP[M][M] = { false }; //DP[len1+1][len2+1]
DP[0][0] = true;
for (int i = 1; i <= len2; )
{
if (pattern[i] == '*')
{
DP[0][i] = DP[0][i-1];
DP[0][i+1] = DP[0][i];
i += 2;
}
else i += 1;
}
for (int i = 1; i <= len1; i++)
{
for (int j = 1; j <= len2;)
{
if (pattern[j] != '*' && pattern[j] != '+')
{
DP[i][j] = (((str[i-1] == pattern[j-1]) || pattern[j-1] == '
.') && DP[i-1][j-1]);
j++;
}
else
{
int iter = i;
if (pattern[j] == '+')
{
if (pattern[j-1] != '.' && pattern[j-1] != str[i-1])
{
j += 2;
continue;
}
else iter--;
}
do
{
if (DP[iter][j-1])
{
DP[i][j] = true;
DP[i][j+1] = true;
break;
}
}
while (iter > 0 && str[iter-- - 1] == pattern[j-1]);
j += 2;
}
}
}
return DP[len1][len2];
}
============================
以前一直觉得很难,发现也不是太难写
x*****0
发帖数: 452
2
mark
h**i
发帖数: 431
3
顶id。。。。

【在 p*****3 的大作中提到】
: //DP矩阵中如果遇到.*或.+, 那么DP[i][j] == DP[i][j+1] = true/false
: const int M = 100;
: bool isMatchDP(const char* str, const char* pattern)
: {
: if (NULL == str || NULL == pattern)
: return false;
: int len1 = strlen(str);
: int len2 = strlen(pattern);
: bool DP[M][M] = { false }; //DP[len1+1][len2+1]
: DP[0][0] = true;

h*******0
发帖数: 270
4
目测是八百题大牛的马甲。。
c********p
发帖数: 1969
5
mark
J****3
发帖数: 427
6
顶!头像也很稀饭!
h***u
发帖数: 9
7
mark
p*****3
发帖数: 488
8

真有眼光,
头像是精心挑选的!

【在 J****3 的大作中提到】
: 顶!头像也很稀饭!
e*****n
发帖数: 316
9
我也喜欢这个头像!
j********x
发帖数: 2330
10
这是2爷的新id?
相关主题
求教电面遇到的一道pattern match的实现讨论一道两个linked list的题目
求两个程序的C++ code专家们,find the longest common substring of two strings
airBnb电面面经两个Sorted Array,找K smallest element
进入JobHunting版参与讨论
k*j
发帖数: 153
11
贴一个从后往前的DPcode。与lz的解法大同小异
class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function

int len1 = strlen(s);
int len2 = strlen(p);
int i,j;
vector > result(len1+1,vector (len2+1,0));
result[len1][len2] = 1;
for(j = len2-1;j>=0;j--){
if(*(p+j+1)=='*'){
result[len1][j] = result[len1][j+2];
}
}
for(i = len1-1;i>=0;i--){
for(j = len2-1;j>=0;j--){
if(*(p+j)=='.'){
if(*(p+j+1)=='*'){
result[i][j] = result[i+1][j];
if(!result[i][j] && j+2<=len2)
result[i][j] = result[i][j+2];
}
else
result[i][j] = result[i+1][j+1];
}
else if(*(p+j)=='*')
result[i][j] = 0;
else{
if(*(p+j)=='*')
result[i][j] = result[i][j+2] || *(p+j)==*(s+i) && result[
i+1][j];
else
result[i][j] = *(p+j)==*(s+i) && result[i+1][j+1];
}
}
}
return result[0][0];
}
};
d****n
发帖数: 233
12
Just curious, what if there is '*' in the s, does it still work?

【在 k*j 的大作中提到】
: 贴一个从后往前的DPcode。与lz的解法大同小异
: class Solution {
: public:
: bool isMatch(const char *s, const char *p) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
:
: int len1 = strlen(s);
: int len2 = strlen(p);
: int i,j;

d****n
发帖数: 233
13
public class Solution {
public boolean isMatch(String s, String p) {
if (p=="") return s == "";

int m = s.length() + 1;
int n = p.length() + 1;
boolean[][] result = new boolean[n][m];

// Initialization part
result[0][0] = true;
result[1][0] = false;

for( int i = 2; i < n; i++)
result[i][0] = p.charAt(i-1) == '*' ? result[i-2][0] : false;

for( int j = 1; j < m; j++){
result[0][j] = false;
result[1][j] = false;
}

if (m > 1)
result[1][1] = match(s.charAt(0), p.charAt(0));

// Major DP part
for( int i = 2; i < n; i++ ){
for( int j = 1; j < m; j++ ){
if(p.charAt(i-1) == '*')
result[i][j] = match(s.charAt(j-1),p.charAt(i-2))?
(result[i][j-1]||result[i-2][j]) : result[i-2][j];
else
result[i][j] = match(s.charAt(j-1),p.charAt(i-1))?
result[i-1][j-1] : false;
}
}
return result[n-1][m-1];
}

boolean match(char a, char b){
return (a == b || b=='.');
}
}
d****n
发帖数: 233
14
Another one for Wildcard match:
public class Solution {
public boolean isMatch(String s, String p) {
int m = s.length() + 1;
int n = p.length() + 1;
boolean[][] result = new boolean[n][m];

result[0][0] = true;
for( int i = 1; i < n; i++){
result[i][0] = p.charAt(i-1) == '*' ? result[i-1][0] : false;
}
for( int j = 1; j < m; j++){
result[0][j] = false;
}
for( int i = 1; i < n; i++ ){
for( int j = 1; j < m; j++ ){
if(p.charAt(i-1) == '*'){
result[i][j] = result[i-1][j]|result[i-1][j-1]|result[i][j-1];
} else
result[i][j] = match(s.charAt(j-1),p.charAt(i-1)) ?
result[i-1][j-1] : false;
}
}
return result[n-1][m-1];
}

boolean match(char a, char b){
return (a == b || b=='?');
}
}

【在 d****n 的大作中提到】
: public class Solution {
: public boolean isMatch(String s, String p) {
: if (p=="") return s == "";
:
: int m = s.length() + 1;
: int n = p.length() + 1;
: boolean[][] result = new boolean[n][m];
:
: // Initialization part
: result[0][0] = true;

c******o
发帖数: 534
15
顶,晚上来学习

★ 发自iPhone App: ChineseWeb 7.8

【在 p*****3 的大作中提到】
: //DP矩阵中如果遇到.*或.+, 那么DP[i][j] == DP[i][j+1] = true/false
: const int M = 100;
: bool isMatchDP(const char* str, const char* pattern)
: {
: if (NULL == str || NULL == pattern)
: return false;
: int len1 = strlen(str);
: int len2 = strlen(pattern);
: bool DP[M][M] = { false }; //DP[len1+1][len2+1]
: DP[0][0] = true;

1 (共1页)
进入JobHunting版参与讨论
相关主题
做题做得很郁闷,求指点经典面试题
50行code能解决addbinary 问题么求教电面遇到的一道pattern match的实现
问一道题(2)求两个程序的C++ code
再帖一遍Amazon Onsite的题airBnb电面面经
aababccbc remove abc讨论一道两个linked list的题目
求教一个string match 的 dp 解法专家们,find the longest common substring of two strings
问个题?两个Sorted Array,找K smallest element
这题谁知道答案?求一题的完美简洁解答
相关话题的讨论汇总
话题: dp话题: result话题: int话题: pattern话题: len2