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

leetcode題解||Regular Expression Matching 問題

編輯:關於C++

problem:

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

thinking:

吐槽幾句:

字符串匹配,'.'和'*'的意義很簡單,不用陳述,但:

isMatch("aab", "c*a*b") → true

算哪門子事?

leetcode (http://articles.leetcode.com/2011/09/regular-expression-matching.html)已有好多人在爭論,這C*是不是可以代表0個C,我TM無語了。

最後的感覺就是這道題為了宣傳那個特定的算法而把條件改了?

PS: 看錯題目了.....2B了


(1)沒有*的情況很好解決,難在怎麼處理*

(2)比如ABBC與 A*C、A*BC,很清楚,利用深搜的思想,只要把BB與*、*B整體作匹配就OK了

自己寫了個測試程序,官方的那個扯淡條件通不過

#include 
#include 
using namespace std;
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int n=0;
        int m=0;
        int index=0;
        while(*(s+n)!='\0')
        {
            n++;
        }
        while(*(p+m)!='\0')
        {
            m++;
        }
       // cout<<"n: "<
我測試了幾組,通過了,歡迎找BUG。


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