leetcode 10. Regular Expression Matching

桃扇骨 2022-07-28 11:58 293阅读 0赞

Implement regular expression matching with support for '.' and '*'.

  1. '.' Matches any single character.
  2. '*' Matches zero or more of the preceding element.
  4. The matching should cover the entire input string (not partial).
  6. The function prototype should be:
  7. bool isMatch(const char *s, const char *p)
  9. Some examples:
  10. isMatch("aa","a") → false
  11. isMatch("aa","aa") → true
  12. isMatch("aaa","aa") → false
  13. isMatch("aa", "a*") → true
  14. isMatch("aa", ".*") → true
  15. isMatch("ab", ".*") → true
  16. isMatch("aab", "c*a*b") → true

这题挺难的，虽然我写的迭代算法效率还算高，但他妈的又臭又长，实在懒得看第二遍,就让它过了吧。

445 / 445 test cases passed.
Status: Accepted
Runtime: 28 ms 

  1. class Solution {
  2.     bool do_once(vector<pair<string, string>>&candi, set<pair<string, string>>&hist)
  3.     {
  4.         vector<pair<string, string>>newcandi;
  5.         for (int i = candi.size()-1; i >=0; i--)
  6.         {
  7.             string ss = candi[i].first;
  8.             string pp = candi[i].second;
  9.             if (ss == pp)
  10.                 return true;
  11.             if (pp.find('.') == string::npos&&pp.find('*') == string::npos)
  12.                 continue;
  13.             int hh = 0;
  14.             int cc1 = 0;
  15.             while (hh < pp.length() && pp[hh] == '.' || pp[hh] == '*')
  16.             {
  17.                 cc1 += pp[hh] == '*' ? 1 : 0;
  18.                 hh++;
  19.             }
  20.             if (hh == pp.length())
  21.             {
  22.                 if (cc1>0&&ss.length() >= pp.length() - 2 * cc1)
  23.                     return true;
  24.                 if (cc1 == 0 && ss.length() == pp.length())
  25.                     return true;
  26.                 continue;
  27.             }
  28.             int hr = hh;
  29.             while (hr < pp.length() && pp[hr] != '.'&&pp[hr] != '*')
  30.                 hr++;
  31.             if (hr < pp.length() && pp[hr] == '*')
  32.             {
  33.                 string str = string(pp.begin() + hh, pp.begin() + hr - 1);
  34.                 string ggg = string(pp.begin() + hr + 1, pp.end());
  35.                 int bbb = 0;
  36.                 if (hh == 0)
  37.                 {
  38.                     while (ss.length() >= str.length()+bbb)
  39.                     {
  40.                         string str1 = str + string(bbb, pp[hr - 1]);
  41.                         if (string(ss.begin(), ss.begin() + str1.length()) == str1)
  42.                         {
  43.                             string gg = string(ss.begin() + str1.length(), ss.end());
  44.                             if (hist.find(pair<string, string>(gg, ggg)) == hist.end())
  45.                             {
  46.                                 hist.insert(pair<string, string>(gg, ggg));
  47.                                 newcandi.push_back(pair<string, string>(gg, ggg));
  48.                             }
  49.                         }
  50.                         else
  51.                             break;
  52.                         bbb++;
  53.                     }
  54.                 }
  55.                 else
  56.                 {
  57.                     if (cc1 > 0)
  58.                         while (true)
  59.                         {
  60.                             string str1 = str + string(bbb, pp[hr - 1]);
  61.                             int pos = ss.find(str1);
  62.                             if (pos != string::npos)
  63.                             {
  64.                                 while (pos != string::npos)
  65.                                 {
  66.                                     if (pos >= hh - 2 * cc1)
  67.                                     {
  68.                                         string gg = string(ss.begin() + pos+str1.length(), ss.end());
  69.                                         if (hist.find(pair<string, string>(gg, ggg)) == hist.end())
  70.                                         {
  71.                                             hist.insert(pair<string, string>(gg, ggg));
  72.                                             newcandi.push_back(pair<string, string>(gg, ggg));
  73.                                         }
  74.                                     }
  75.                                     pos = ss.find(str1, pos + 1);
  76.                                 }
  77.                             }
  78.                             else
  79.                                 break;
  80.                             bbb++;
  81.                         }
  82.                     else
  83.                     {
  84.                         while (hh + str.length() + bbb <= ss.length())
  85.                         {
  86.                             string str1 = str + string(bbb, pp[hr - 1]);
  87.                             if (string(ss.begin() + hh, ss.begin() +hh+ str1.length()) == str1)
  88.                             {
  89.                                 string gg = string(ss.begin() + hh + str1.length(), ss.end());
  90.                                 if (hist.find(pair<string, string>(gg, ggg)) == hist.end())
  91.                                 {
  92.                                     hist.insert(pair<string, string>(gg, ggg));
  93.                                     newcandi.push_back(pair<string, string>(gg, ggg));
  94.                                 }
  95.                             }
  96.                             else
  97.                                 break;
  98.                             bbb++;
  99.                         }
  100.                     }
  101.                 }
  102.             }
  103.             else
  104.             {
  105.                 string str = string(pp.begin() + hh, pp.begin() + hr);
  106.                 string ggg = string(pp.begin() + hr, pp.end());
  107.                 if (hh == 0)
  108.                 {
  109.                     if (string(ss.begin(), ss.begin() + str.length()) == str)
  110.                     {
  111.                         string gg = string(ss.begin() + str.length(), ss.end());
  112.                         if (hist.find(pair<string, string>(gg, ggg)) == hist.end())
  113.                         {
  114.                             hist.insert(pair<string, string>(gg, ggg));
  115.                             newcandi.push_back(pair<string, string>(gg, ggg));
  116.                         }
  117.                     }
  118.                 }
  119.                 else
  120.                 {
  121.                     if (cc1 > 0)
  122.                     {
  123.                         int pos = ss.find(str);
  124.                         if (pos != string::npos)
  125.                         {
  126.                             while (pos != string::npos)
  127.                             {
  128.                                 if (pos >= hh - 2 * cc1)
  129.                                 {
  130.                                     string gg = string(ss.begin() + pos + str.length(), ss.end());
  131.                                     if (hist.find(pair<string, string>(gg, ggg)) == hist.end())
  132.                                     {
  133.                                         hist.insert(pair<string, string>(gg, ggg));
  134.                                         newcandi.push_back(pair<string, string>(gg, ggg));
  135.                                     }
  136.                                 }
  137.                                 pos = ss.find(str, pos + 1);
  138.                             }
  139.                         }
  140.                     }
  141.                     else
  142.                     {
  143.                         if (string(ss.begin() + hh, ss.begin() + hh + str.length()) == str)
  144.                         {
  145.                             string gg = string(ss.begin() + hh + str.length(), ss.end());
  146.                             if (hist.find(pair<string, string>(gg, ggg)) == hist.end())
  147.                             {
  148.                                 hist.insert(pair<string, string>(gg, ggg));
  149.                                 newcandi.push_back(pair<string, string>(gg, ggg));
  150.                             }
  151.                         }
  152.                     }
  153.                 }
  154.             }
  155.         }
  156.         candi = newcandi;
  157.         return false;
  158.     }
  159. public:
  160.     bool isMatch(string s, string p) {
  161.         if (s == p)
  162.             return true;
  163.         int pos = p.find('*');
  164.         while (pos != string::npos)
  165.         {
  166.             if (pos + 2 < p.length() && p[pos - 1] == p[pos + 1] && p[pos] == p[pos + 2])
  167.                 p.erase(pos + 1, 2);
  168.             else
  169.                 pos = p.find('*', pos + 1);
  170.         }
  171.         vector<pair<string, string>>candi;
  172.         candi.push_back(pair<string, string>(s, p));
  173.         bool f = false;
  174.         set<pair<string, string>>hist;
  175.         while (!candi.empty()&&!f)
  176.         {
  177.             f = do_once(candi,hist);
  178.         }
  179.         return f;
  180.     }
  181. };

发表评论

表情：
评论列表 （有 0 条评论，293人围观）

还没有评论，来说两句吧...

相关阅读