LeetCode Problem 10, Regular Expression Matching<\/a>.<\/p>\nProblem<\/h3>\n
Given an alphabet string and a simplified version of regular expression. Check if the string match the regular expression.<\/p>\n
In the simplified version of regular expressions, there are only three type of elements: (1) a letter, matching a letter, (2) a dot, matching any letter (3) a letter or a dot followed by a star, matching zero or more copies of that letter, or any letter if it\u2019s a dot.<\/p>\n
Solution<\/h3>\n
This is a typical DP problem. Let\u00a0f(i,j)<\/em>\u00a0be whether the prefix of length\u00a0i<\/em>\u00a0of the string match the prefix of length\u00a0j<\/em>\u00a0of the regular expression.<\/p>\nThe base case is f(0,0)=true.<\/p>\n
For the recursive step, if the\u00a0j<\/em>-th element of is a letter or a dot, then we simply check if the\u00a0i<\/em>-th element of the string matches and check if\u00a0f(i-1, j-1)<\/em>\u00a0is true.<\/p>\nIf the\u00a0j<\/em>-th element of is a star, then we check\u00a0f(i, j-2)<\/em>\u00a0to see if we can match the string without that star, and then we check if the\u00a0(i-1)<\/em>-th element matches and check\u00a0f(j-1, j)<\/em>\u00a0is true.<\/p>\nSource Code<\/h3>\n
The source code is in C++. Instead of writing in a recursive manner, I wrote the program in the other direction because it\u2019s easier to write.<\/p>\n
\nbool isMatch(string s, string p) {\n std::vector<std::vector > \n f(s.size()+1, std::vector(p.size()+1, false));\n f[0][0] = true;\n for (int i = 0; i <= s.size(); ++i) \n for (int j = 0; j <= p.size(); ++j) \n if (f[i][j]) {\n if (i < s.size() && j < p.size() \n && (s[i] == p[j] || p[j] == '.') )\n f[i+1][j+1] = true;\n if (j < p.size()-1 && p[j+1] == '*')\n f[i][j+2] = true;\n if (i < s.size() && j > 1 && p[j-1] == '*' \n && (p[j-2] == s[i] || p[j-2] == '.') )\n f[i+1][j] = true;\n }\n return f[s.size()][p.size()];\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"LeetCode has become the de facto go-to website for tech interviews. As a former competitive programmer, the LeetCode \u201chard\u201d, \u201cmedium\u201d, and \u201ceasy\u201d problems are more like \u201ceasy\u201d, \u201cvery easy\u201d, \u201cextremely easy\u201d for me. I think it would be a good idea for me to put my solutions of some of the LeetCode hard problems here. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-23","post","type-post","status-publish","format-standard","hentry","category-coding"],"_links":{"self":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts\/23","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=23"}],"version-history":[{"count":3,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts\/23\/revisions"}],"predecessor-version":[{"id":133,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts\/23\/revisions\/133"}],"wp:attachment":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=23"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=23"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=23"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}