由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 已经用了dp,我的wildcard怎么还是过不了大oj
相关主题
leetcode regular expression match的问题wildcard string matching,谁有最简洁的非递归解法?
wildcard matching 大case runtime error一道字符串题目
Leetcode Timeout看看这个题目 我的算法在2楼 大牛们有没有建议改进我的算法
Wildcard Matching 和 Regular Expression Matching 区别是什么Wildcard Matching题求助
leetcode上wild matchLeetcode-010: Regular Expression Match (DP Solution)
贡献个regular expression DP解法regular expression mathinc --Java写竟然超时了/。
java没有指针真麻烦贴几道某大公司的面试题
实现regex(.*+)和wildcard(?*)匹配的题isMatch("ab", ".*") → true 为什么是true???
相关话题的讨论汇总
话题: dp话题: true话题: int话题: blc话题: flag
进入JobHunting版参与讨论
1 (共1页)
c********p
发帖数: 1969
1
求帮助
c********p
发帖数: 1969
2
上代码,大家批斗!
public class Solution {
public boolean isMatch(String s, String p) {
// Start typing your Java solution below
// DO NOT write main() function
if(s == null || p == null){
return false;
}

int slen = s.length();
int plen = p.length();
boolean[][] dp = new boolean[slen + 1][plen + 1];
dp[0][0] = true;
for(int i = 1; i <= plen; i++){
if(p.charAt(i - 1) == '*'){
if( dp[0][i - 1]== true){
dp[0][i] = true;
}
}
}

for(int i = 1; i <= s.length(); i++){
for(int j = 1; j <= p.length(); j++){
if((p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j
- 1)) && dp[i - 1][j - 1] == true){
dp[i][j] = true;
}else if(p.charAt(j - 1) == '*'){
for(int k = 0; k < i; k++){
if(dp[k][j - 1] == true){
dp[i][j] = true;
break;
}
if(dp[i][j - 1] == true){
dp[i][j] = true;
}
}
}
}
}
return dp[slen][plen];
}
}

【在 c********p 的大作中提到】
: 求帮助
p*****3
发帖数: 488
3

我觉得你好牛,这题用dp不容易,膜拜一下

【在 c********p 的大作中提到】
: 求帮助
p*****2
发帖数: 21240
4
dp过不了吧?要O(n)才行
p*****3
发帖数: 488
5

确定不是O(1)?

【在 p*****2 的大作中提到】
: dp过不了吧?要O(n)才行
c********p
发帖数: 1969
6
就是过不了啊,才问你怎么办啊!

【在 p*****2 的大作中提到】
: dp过不了吧?要O(n)才行
p*****2
发帖数: 21240
7

不用办。这样就可以了。

【在 c********p 的大作中提到】
: 就是过不了啊,才问你怎么办啊!
c********p
发帖数: 1969
8
怎么O(n)?
我的确实过不了大oj,我的n^2

【在 p*****2 的大作中提到】
:
: 不用办。这样就可以了。

c********p
发帖数: 1969
9
你怎么做的这个题?
怎么过的大oj?

【在 p*****3 的大作中提到】
:
: 确定不是O(1)?

p*****2
发帖数: 21240
10

我感觉不用追求O(n), 面试dp就可以了

【在 c********p 的大作中提到】
: 怎么O(n)?
: 我的确实过不了大oj,我的n^2

相关主题
贡献个regular expression DP解法wildcard string matching,谁有最简洁的非递归解法?
java没有指针真麻烦一道字符串题目
实现regex(.*+)和wildcard(?*)匹配的题看看这个题目 我的算法在2楼 大牛们有没有建议改进我的算法
进入JobHunting版参与讨论
c********p
发帖数: 1969
11
告诉偶,好么。。。。
献上一束花~

【在 p*****2 的大作中提到】
:
: 我感觉不用追求O(n), 面试dp就可以了

c********p
发帖数: 1969
12
是说滚动数组么?

【在 p*****2 的大作中提到】
:
: 我感觉不用追求O(n), 面试dp就可以了

p*****2
发帖数: 21240
13

greedy

【在 c********p 的大作中提到】
: 告诉偶,好么。。。。
: 献上一束花~

i********s
发帖数: 22
14
这个题目比较恶心,O(N*N)超内存,直接DP超时。
我在DP基础上做了一个长度剪枝,通过大数据,感觉是OJ上有些比较tricky的case;
附上我的解答;
https://github.com/xiongjunliang/leetcode/blob/master/wildcardmatch/
wildcardmatch2.cpp
g**G
发帖数: 767
15
这种问题用二维数组确实太浪费空间了,不是一种好做法
设想你匹配一个1M的文件和一个100个char的pattern,光数组就要开100M ,但其中只
有一条路线是标记了的,其他空间的都浪费了
f*******b
发帖数: 520
16
这题是要上DP的,LZ用的方法和我开始一样,但通过不了大数据,不是DP的问题,是所
用算法本身的问题,我改了后就能过大数据了:
public boolean isMatch(String s, String p) {
int count=0;
for(int i=0;i if(p.charAt(i)!='*') count++;
if(count>s.length()) return false;
if(s.length()==0) return true;
if(p.length()==0) return s.length()==0;
boolean[][] blc=new boolean[s.length()+1][p.length()+1];
blc[0][0]=true;
for(int j=1;j for(int i=1;i if(p.charAt(j-1)=='*'){
if(blc[i-1][j-1]==true){
for(int m=i-1;m<=s.length();m++) blc[m][j]=true;
break;
}
if(blc[i][j-1]==true){
for(int m=i;m<=s.length();m++) blc[m][j]=true;
break;
}
}
else{
if((p.charAt(j-1)==s.charAt(i-1)||p.charAt(j-1)=='?')&&
blc[i-1][j-1]==true) blc[i][j]=true;
}
}
}
return blc[s.length()][p.length()];
}
r**d
发帖数: 316
17
如果按列dp的话,不用保存整个二维数组,只要保存两个一维数组即可,一个是当前列
,一个是前一列。

【在 i********s 的大作中提到】
: 这个题目比较恶心,O(N*N)超内存,直接DP超时。
: 我在DP基础上做了一个长度剪枝,通过大数据,感觉是OJ上有些比较tricky的case;
: 附上我的解答;
: https://github.com/xiongjunliang/leetcode/blob/master/wildcardmatch/
: wildcardmatch2.cpp

s*******s
发帖数: 1031
18
我的C++代码:
class Solution {
public:
bool isMatch(const char *s, const char *p) {
int ptnCnt = 0;
const char *pp = p;
while(pp && (*pp)) {
if(*pp != '*')
++ptnCnt;
++pp;
}

int strCnt = 0;
if(s)
strCnt = strlen(s);

if(strCnt < ptnCnt)
return false;

if(!strCnt)
return !ptnCnt;
if(!ptnCnt)
return strlen(p);

int n = strCnt;
vector > M(2, vector(n+1, false));
M[0][0] = true;
int flag = 1;
pp = p;
while(pp && *pp) {
if(*pp == '*') {
int i = 0;
while(i<=n && !M[!flag][i]) {
M[flag][i] = false;
++i;
}
while(i<=n) {
M[flag][i] = true;
++i;
}
} else {
M[flag][0] = false;
for(int i=1; i<=n; ++i) {
if(*pp=='?' || *pp==s[i-1])
M[flag][i] = M[!flag][i-1];
else
M[flag][i] = false;
}
}
flag = !flag;
++pp;
}
return M[!flag][n];
}
};

【在 c********p 的大作中提到】
: 上代码,大家批斗!
: public class Solution {
: public boolean isMatch(String s, String p) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(s == null || p == null){
: return false;
: }
:
: int slen = s.length();

c********p
发帖数: 1969
19
谢谢楼上各位!
c********p
发帖数: 1969
20
我刚看了一下你的代码,没太看懂为什么这样做。
根据p 的长度,得出是一行还是2行,可是为啥这么做?是不是也相当于是滚动数组呢?

【在 i********s 的大作中提到】
: 这个题目比较恶心,O(N*N)超内存,直接DP超时。
: 我在DP基础上做了一个长度剪枝,通过大数据,感觉是OJ上有些比较tricky的case;
: 附上我的解答;
: https://github.com/xiongjunliang/leetcode/blob/master/wildcardmatch/
: wildcardmatch2.cpp

相关主题
Wildcard Matching题求助贴几道某大公司的面试题
Leetcode-010: Regular Expression Match (DP Solution)isMatch("ab", ".*") → true 为什么是true???
regular expression mathinc --Java写竟然超时了/。问一道题
进入JobHunting版参与讨论
c********p
发帖数: 1969
21
其实,也就是说,只差在一个地方,就是在最最开始,要count一下非*的字符个数,
比较s的长度。
只有这个地方有问题,是吧?

【在 f*******b 的大作中提到】
: 这题是要上DP的,LZ用的方法和我开始一样,但通过不了大数据,不是DP的问题,是所
: 用算法本身的问题,我改了后就能过大数据了:
: public boolean isMatch(String s, String p) {
: int count=0;
: for(int i=0;i: if(p.charAt(i)!='*') count++;
: if(count>s.length()) return false;
: if(s.length()==0) return true;
: if(p.length()==0) return s.length()==0;
: boolean[][] blc=new boolean[s.length()+1][p.length()+1];

c********p
发帖数: 1969
22
滚动数组,是么?

【在 r**d 的大作中提到】
: 如果按列dp的话,不用保存整个二维数组,只要保存两个一维数组即可,一个是当前列
: ,一个是前一列。

r**d
发帖数: 316
23
是的

【在 c********p 的大作中提到】
: 滚动数组,是么?
1 (共1页)
进入JobHunting版参与讨论
相关主题
isMatch("ab", ".*") → true 为什么是true???leetcode上wild match
问一道题贡献个regular expression DP解法
一道题目java没有指针真麻烦
写了一下leetcode上Valid Number,用boolean表示一些状态是不是比较简单实现regex(.*+)和wildcard(?*)匹配的题
leetcode regular expression match的问题wildcard string matching,谁有最简洁的非递归解法?
wildcard matching 大case runtime error一道字符串题目
Leetcode Timeout看看这个题目 我的算法在2楼 大牛们有没有建议改进我的算法
Wildcard Matching 和 Regular Expression Matching 区别是什么Wildcard Matching题求助
相关话题的讨论汇总
话题: dp话题: true话题: int话题: blc话题: flag