Solution to the famous LeetCode hard problem Regular-Expression-Matching in C++.
explanation (Beats 100% Space Optimized.)
This code is a C++ implementation of a dynamic programming solution to solve the regular expression matching problem. The function isMatch takes in two strings s and p as input and returns a boolean value indicating whether s matches the pattern specified in p or not.
The algorithm uses a 2D dynamic programming approach where the state of the DP is stored in a vector curr of size n+1, where n is the length of the pattern p. The value of curr[j] represents whether the substring of s of length i matches the substring of p of length j.
The outer loop iterates through each character of string s, and the inner loop iterates through each character of string p. At each iteration, the value of curr[j] is computed based on the previous states of curr[j] and curr[j-1] (which represent the current and previous characters of the pattern p respectively) and the previous value of curr[j] (which represents the previous row of the DP matrix).
If p[j-1] is a '' character, then the value of curr[j] is computed by looking at the value of curr[j-2] (which represents the case where the '' character matches 0 occurrences of the previous character) and the value of curr[j] in the previous row (which represents the case where the '' character matches one or more occurrences of the previous character). If the previous character is a dot . or matches the current character of s, then the '' character can match multiple occurrences of the previous character.
If p[j-1] is not a '*' character, then the value of curr[j] is computed by checking if the current character of s matches the current character of p or if the current character of p is a dot ..
Finally, the function returns the value of curr[n], which represents whether the entire string s matches the entire pattern p.
The time complexity of this algorithm is O(m*n), where m and n are the lengths of the strings s and p respectively, and the space complexity is O(n), where n is the length of the string p.
Solution to the famous LeetCode hard problem Regular-Expression-Matching in C++.
explanation (Beats 100% Space Optimized.)
This code is a C++ implementation of a dynamic programming solution to solve the regular expression matching problem. The function
isMatchtakes in two stringssandpas input and returns a boolean value indicating whethersmatches the pattern specified inpor not.The algorithm uses a 2D dynamic programming approach where the state of the DP is stored in a vector
currof sizen+1, wherenis the length of the patternp. The value ofcurr[j]represents whether the substring ofsof lengthimatches the substring ofpof lengthj.The outer loop iterates through each character of string
s, and the inner loop iterates through each character of stringp. At each iteration, the value ofcurr[j]is computed based on the previous states ofcurr[j]andcurr[j-1](which represent the current and previous characters of the patternprespectively) and the previous value ofcurr[j](which represents the previous row of the DP matrix).If
p[j-1]is a '' character, then the value ofcurr[j]is computed by looking at the value ofcurr[j-2](which represents the case where the '' character matches 0 occurrences of the previous character) and the value ofcurr[j]in the previous row (which represents the case where the '' character matches one or more occurrences of the previous character). If the previous character is a dot.or matches the current character ofs, then the '' character can match multiple occurrences of the previous character.If
p[j-1]is not a '*' character, then the value ofcurr[j]is computed by checking if the current character ofsmatches the current character ofpor if the current character ofpis a dot..Finally, the function returns the value of
curr[n], which represents whether the entire stringsmatches the entire patternp.The time complexity of this algorithm is O(m*n), where
mandnare the lengths of the stringssandprespectively, and the space complexity is O(n), wherenis the length of the stringp.