leetcode-no11（DP）

发表于 | 更新于: | 分类于 ， ， | | 阅读次数: |
字数统计: 669 | 阅读时长 ≈ 4
problem： Regular Expression Matching

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.
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

code: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*函数声明 */ 
bool isMatch(char* s, char* p);

int main(int argc, char* argv[]) 
{
	printf("\n---------------通配符匹配算法---------------\n");
	printf("请输入待匹配串：\n");
	char *s;
	scanf("%s",&s);
	printf("请输入匹配串：\n");	
	char *p;
	scanf("%s",&p); 
	
	bool isMatchRes = isMatch(s, p); 
	printf("算法匹配结果：%d\n", isMatchRes);
	
	// test_1();
	
	printf("\n---------------通配符匹配算法---------------\n");
	
    system("pause"); 
    return 0; 
} 

//////////////////////////////////// 通配符算法一 ////////////////////////////////
bool helper(char* s, char* p, int i, int j, int sl, int pl, bool** mark) {
  if(i == sl && j == pl) return true; // Exhaust both at the same time
  if(i > sl || j >= pl) return false; // return false if i and j reach corresponding lengths
  // except when i == sl and j < pl

  if(mark[i][j]) return false; // Do not want to do repeating job
  mark[i][j] = true;
  if(j < pl - 1 && p[j + 1] == '*') {
    if(s[i] == p[j] || p[j] == '.') { // If p[j] works for s[i]
      return helper(s, p, i, j + 2, sl, pl, mark) // Ignore the star
          || helper(s, p, i + 1, j, sl, pl, mark) // Continue hanging out with the star
          || helper(s, p, i + 1, j + 2, sl, pl, mark); // p[j] and p[j+1] works like a '.'
    }
    return helper(s, p, i, j + 2, sl, pl, mark); // If p[j] does not work, ignore the star
  }
  if(s[i] == p[j] || p[j] == '.') return helper(s, p, i + 1, j + 1, sl, pl, mark); // If p[j] works, proceed
  return false;
}

bool isMatch_1(char* s, char* p) {
  int sl = strlen(s);
  int pl = strlen(p);
  // 2D list to keep track of the pairs of indices that have been visited
  bool** mark = (bool**) calloc(sl + 1, sizeof(bool*));
  for(int i = 0; i < sl + 1; i++) {
    mark[i] = (bool*) calloc(pl + 1, sizeof(bool));
    for(int j = 0; j < pl + 1; j++) {
      mark[i][j] = false;
    }
  }
  bool res = helper(s, p, 0, 0, sl, pl, mark);
  // Free stuff
  for(int i = 0; i < sl + 1; i++) {
    free(mark[i]);
  }
  free(mark);
  return res;
}

//////////////////////////////////// 通配符算法二 ////////////////////////////////
bool isMatch(char *s, char *p)
{
	int s_len = 0, p_len = 0;
	while(s[s_len] != 0) s_len++;
	while(p[p_len] != 0) p_len++;
	s_len++;p_len++;

	bool m[p_len][s_len];
	memset(m, 0, p_len*s_len);
	m[0][0] = true;
	for (int i = 1 ; i < p_len ; i++)
		m[i][0] = i > 1 && p[i-1] == '*' && m[i-2][0] ? true : false;

	for (int i = 1 ; i < p_len ; i++)
	{
		for (int j = 1 ; j < s_len ; j++)
		{
			if (p[i-1] != '*')
				m[i][j] = m[i-1][j-1] && (p[i-1] == '.' || p[i-1] == s[j-1]);
			else
				m[i][j] = m[i-2][j] || ((m[i-2][j-1] || m[i][j-1]) && (p[i-2] == '.' || p[i-2] == s[j-1]));
		}
	}

	return m[p_len-1][s_len-1];
}

the end