2014
11-18

LeetCode-Regular Expression Matching[字符串]

Regular Expression Matching

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


// LeetCode, Regular Expression Matching
// 递归版，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if (*p == '\0') return *s == '\0';

// next char is not '*', then must match current character
if (*(p + 1) != '*') {
if (*p == *s || (*p == '.' && *s != '\0'))
return isMatch(s + 1, p + 1);
else
return false;
} else { // next char is '*'
while (*p == *s || (*p == '.' && *s != '\0')) {
if (isMatch(s, p + 2))
return true;
s++;
}
return isMatch(s, p + 2);
}
}
};


Java代码:

public class Solution {
public boolean isMatch(String s, String p) {
if(s.length()==0 && p.length()==0)
return true;
if(p.length()==0)
return false;
boolean[][] res = new boolean[s.length()+1][p.length()+1];
res[0][0] = true;
for(int j=0;j<p.length();j++)
{
if(p.charAt(j)=='*')
{
if(j>0 && res[0][j-1]) res[0][j+1]=true;
if(j<1) continue;
if(p.charAt(j-1)!='.')
{
for(int i=0;i<s.length();i++)
{
if(res[i+1][j] || j>0&&res[i+1][j-1]
|| i>0 && j>0 && res[i][j+1]&&s.charAt(i)==s.charAt(i-1)&&s.charAt(i-1)==p.charAt(j-1))
res[i+1][j+1] = true;
}
}
else
{
int i=0;
while(j>0 && i<s.length() && !res[i+1][j-1] && !res[i+1][j])
i++;
for(;i<s.length();i++)
{
res[i+1][j+1] = true;
}
}
}
else
{
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)==p.charAt(j) || p.charAt(j)=='.')
res[i+1][j+1] = res[i][j];
}
}
}
return res[s.length()][p.length()];
}
}

1. 你好，代码1的时间复杂度不是O(n)， 最坏的情况是O(n^2)比如这组样例，“aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa”， “.*a”； 如有不对，请告知；

2. #include <stdio.h>
int main()
{
int n,p,t[100]={1};
for(int i=1;i<100;i++)
t =i;
while(scanf("%d",&n)&&n!=0){
if(n==1)
printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
else {
if(n%4) p=n/4+1;
else p=n/4;
int q=4*p;
printf("Printing order for %d pages:n",n);
for(int i=0;i<p;i++){
printf("Sheet %d, front: ",i+1);
if(q>n) {printf("Blank, %dn",t[2*i+1]);}
else {printf("%d, %dn",q,t[2*i+1]);}
q–;//打印表前
printf("Sheet %d, back : ",i+1);
if(q>n) {printf("%d, Blankn",t[2*i+2]);}
else {printf("%d, %dn",t[2*i+2],q);}
q–;//打印表后
}
}
}
return 0;
}

3. “可以发现,树将是满二叉树,”这句话不对吧，构造的树应该是“完全二叉树”，而非“满二叉树”。