程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [LeetCode] Regular Expression Matching

[LeetCode] Regular Expression Matching

編輯:關於C++

 

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

解題思路:

題意為實現正則表達式的匹配。其中支持.和*

分成三種情況。設當前字符串和模式的下標分別為i,j

1、若當前模式匹配完畢,即p[j]=='\0',若字符串結束,則返回true,否則返回false

2、若模式的下一個字符不是*,即p[j+1]!='*'。這裡分情況討論。

(1) 若s[i]==p[j],遞歸驗證i+1, j+1

(2) 若p[i]=='.'且s[i]!='\0',遞歸驗證i+1, j+1

(3) 否則,返回false

3、若模式的下一個字符是*,即p[j+1]=='*',則不斷通過遞歸回溯i+k,j+2(k從0增長至len(s)-i,j+2意味著越過當前字符和*)。

代碼如下:

 

class Solution {
public:
    bool isMatch(string s, string p) {
        return matchHelper(s, p, 0, 0);
    }
    
    bool matchHelper(string& s, string& p, int i, int j){
        if(p[j]=='\0'){
            return s[i]=='\0';
        }
        
        if( p[j + 1] != '*'){
            return ((s[i] == p[j]) || (p[j] == '.' && s[i]!='\0')) && matchHelper(s, p, i + 1, j + 1);
        }
        
        while((s[i] == p[j]) || (p[j] == '.' && s[i]!='\0')){
            if(matchHelper(s, p, i, j+2)) return true;
            i++;
        }
        return matchHelper(s, p, i, j+2);
    }
};


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved