Leetcode#10 Regular Expression Matching

원제 주소
 
이 문제는 나를 오랫동안 곤경에 빠뜨렸다. 한 그룹의 테스트 데이터가 로컬에서 뛰는 결과는true였지만, Letcode 서버에서 뛰는 결과는false여서, 나는 백 번 생각해도 이해할 수 없었다.나중에 한참이 걸려서야 원인을 찾았는데 원래는 자신의 코드가 엄격하지 않았다. 코드를 간결하게 하기 위해 문장의 기본 빈 메모리가 0이라는 판단이 있었는데 결과는 틀렸다.
 
이 문제는 기교가 없고 일치하는 사고방식이 직관적이다. 만약에 현재 문자가 *라면 바로 건너간다.*가 아닌 경우 어떻게 처리해야 하는지 다음 문자가 맞는지 확인해야 합니다.*
1. 만약 다음 문자가 *이 아니라면 이 문자는 일치할 수 있어야 한다. 그리고 계속한다.만약 다음 문자가 *라면, 이 문자는 0, 1, 2, 3과 일치해야 한다.계속 시도하다
코드:

 1 bool matchp(const char *s, const char *p) {

 2   if (!*s) {

 3     while (*p && (*p == '*' || *(p + 1) == '*'))

 4       p++;

 5     return !*p;

 6   }

 7   else if (!*p)

 8     return false;

 9 

10   if (*p == '*')

11     return matchp(s, p + 1);

12 

13   if (*(p + 1) != '*')

14     return (*p == '.' || *s == *p) && matchp(s + 1, p + 1);

15   else {

16     do {

17       if (matchp(s, p + 2))

18         return true;

19       s++;

20     } while (*(s - 1) && (*p == '.' || *(s - 1) == *p));

21     return false;

22   }

23 }

24 

25 bool isMatch(const char *s, const char *p) {

26   if (!*p)

27     return !*s;

28 

29   return matchp(s, p);

30 }

 
위의 코드는 이미 AC를 할 수 있지만 33ms의 시간을 소모한다. 왜냐하면 특정한 일치하는 열에 대한 효율이 매우 낮기 때문이다. 예를 들어 어떤 열에는 많은 a*b*c*가 포함되어 있기 때문이다.이런 것들이지만 최종 결과는 일치하지 않는다. 이럴 때 알고리즘은 대량의 시간을 낭비하고 되돌아와서 최적화할 수 있다.
나의 방법은 먼저 정규열을 간소화한 다음에 일치하는 것이다.간소화 규칙은 다음과 같습니다.
1. 인접한 여러 개* 하나만 유지.X*Y*와 같은 형식의 경우 X와 Y가 모두 "."이 아닌 경우X와 Y가 같으면 하나만 남는다.예를 들어 a*a*를 a*3으로 간소화했다.X*Y*와 같은 형식의 경우 X와 Y 중 하나가 "."이면"."만 유지됩니다.예: a*.*또는.*a* 모두.*
예를 들어 일치하는 문자열은.*bc*.*b*b*a*.bc*, 간소화 후.*b.*.bc*, 효과는 여전히 뚜렷하다.
 
최적화된 코드:

 1 bool matchp(const char *s, const char *p) {

 2   if (!*s) {

 3     while (*p == '*' || *(p + 1) == '*')

 4       p++;

 5     return !*p;

 6   }

 7   else if (!*p)

 8     return false;

 9 

10   if (*p == '*')

11     return matchp(s, p + 1);

12 

13   if (*(p + 1) != '*')

14     return (*p == '.' || *s == *p) && matchp(s + 1, p + 1);

15   else {

16     do {

17       if (matchp(s, p + 2))

18         return true;

19       s++;

20     } while (*(s - 1) && (*p == '.' || *(s - 1) == *p));

21     return false;

22   }

23 }

24 

25 const char *simplify(const char *p) {

26   string reg;

27   char prev;

28 

29   reg.push_back(*p);

30   prev = *p;

31   for (p++; *p; p++) {

32     if (reg.back() == '*') {

33       if (*p == '*')

34         continue;

35       if (*(p + 1) == '*') {

36         if (*p == '.') {

37           while (reg.back() == '*') {

38             reg.pop_back();

39             reg.pop_back();

40           }

41           prev = *p;

42           reg.push_back(*p);

43         }

44         else if (prev != '.' && *p != prev) {

45           prev = *p;

46           reg.push_back(*p);

47         }

48       }

49       else {

50         prev = *p;

51         reg.push_back(*p);

52       }

53     }

54     else {

55       reg.push_back(*p);

56       if (*p != '*')

57         prev = *p;

58     }

59   }

60 

61   char *res = new char[reg.length()];

62   strcpy(res, reg.c_str());

63 

64   return res;

65 }

66 

67 bool isMatch(const char *s, const char *p) {

68   if (!*p)

69     return !*s;

70 

71   simplify(p); // new

72 

73   return matchp(s, p);

74 }

 
 
최적화 후 9ms 소요