Given a text string containing characters only from lowercase alphabetic characters and a pattern string containing characters only from lowercase alphabetic characters and two other special characters '.' and '*'.
Your task is to implement a pattern matching algorithm that returns true if pattern is matched with text otherwise returns false. The matching must be exact, not partial.
1) '.' - Matches a single character from lowercase alphabetic characters.
2) '*' - Matches zero or more preceding character. It is guaranteed that '*' will have one preceding character which can be any lowercase alphabetic character or special character '.'. But '*' will never be the preceding character of '*'. (That means "**" will never occur in the pattern string.)
'.' = "a", "b", "c", ... , "z".
a* = "a","aa","aaa","aaaa",... or empty string("").
ab* = "a", "ab", "abb", "abbb", "abbbb",...
Input: text = "abbbc" and pattern = "ab*c"
Output: true
Given pattern string can match:
"ac", "abc", "abbc", "abbbc", "abbbbc", ...
Input: text = "abcdefg" and pattern = "a.c.*.*gg*"
Output: true
".*" in pattern can match "", ".", "..", "...", "....", ...
"g*" in pattern can match "", "g", "gg", "ggg", "gggg", ...
Now, consider:
'.' at position 2 as 'b',
'.*' at position {4,5} as "...",
'.*' at position {6,7} as "" and
[g*] at position {8,9} as "".
So, "a.c.*gg*" = "abc...g" where we can write "..." as "def". Hence, both matches.
Input:
text = "abc" and pattern = ".ab*.."
Output: false
If we take 'b*' as "" then also, length of the pattern will be 4 (".a.."). But, given text's length is only 3. Hence, they can not match.
Input Parameters: There are two arguments, first one is string denoting text and second one is string denoting pattern.
Output: Return boolean, true if text and pattern matches exactly, otherwise return false.
● 0 <= text length, pattern length <= 1000
● Text string containing characters only from lowercase alphabetic characters.
● Pattern string containing characters only from lowercase alphabetic characters and two other special characters '.' and '*'
● In pattern string, It is guaranteed that '*' will have one preceding character which can be any lowercase alphabetic character or special character '.'. But '*' will never be the preceding character of '*'.
We provided two solutions.
In both solutions we are making simplified pattern string from pattern string (explained below with examples). Basically, We are removing duplicate '*' character from pattern string and '*' itself also. We are also maintaining isStarChar boolean array to store whether simplified pattern character was followed by '*' in pattern string or not.
e.g. If pattern = [abc*c*c*dd*] then simplified pattern string = "abcdd" and isStarChar = [false, false, true, false, true].
Here, in this example we have removed [c*c*c*] and keep only one [c]. [c]'s position in the simplified pattern string is 3. So, we have stored true at position 3 of isStarChar and also removed '*' from pattern string. Same for character 'd*'.
O(2^(len_simpl_pat + len_text))
O(len_pat + len_text).
We are using one extra character array and one boolean array to make the simplified pattern string. Also, O(len_pat + len_text) space will be used by recursion stack.
O(len_pat + len_text).
As input is O(len_pat + len_text) and auxiliary space used is also O(len_pat + len_text). So, O(len_pat + len_text) + O(len_pat + len_text) -> O(len_pat + len_text).
This solution uses Dynamic Programming. In this method, We build a dp[][] 2D boolean array from top to bottom such that dp[i][j] indicates first i character of text string matches to first j character of pattern string or not.
Here, 3 cases will arise,
dp[i][j-1] is true.
It means first i character of text string matches with first j-1 character of simplified pattern string. So, dp[i][j] will be true if jth character of simplified pattern string is '*', it means isStarChar[j] should be true.
dp[i-1][j-1] is true.
It means first i-1 character of text string matches with first j-1 character of simplified pattern string. So, dp[i][j] will be true if jth character of simplified pattern string matches with ith character of text string. It can only be match if jth character of pattern string is '.' or same as ith character of text string.
Case 3:
dp[i-1][j] is true.
It means first i-1 character of text string matches with first j character of simplified pattern string. So, dp[i][j] will be true if jth character of simplified pattern string is '*' and can be match with ith character of text string. It can only be match if jth character of pattern string is '.' or same as ith character of text string.
O(len_simpl_pat * len_text + (len_simpl_pat + len_text)).
O(len_simpl_pat + len_text) for reading input and simplifying pattern string.
O(len_simpl_pat * len_text + (len_pat + len_text)).
As we are using boolean array of size (len_simpl_pat * len_text) to store dp values, Char array of size len_pat to get simplified pattern string, boolean array of size len_pat to store is that toStarChar or not.
O(len_simpl_pat * len_text + (len_pat + len_text)).
As input is O(len_pat + len_text) and auxiliary space used is O(len_simpl_pat * len_text + (len_pat + len_text)). So, O(len_pat + len_text) + O(len_simpl_pat * len_text + (len_pat + len_text)) -> O(len_simpl_pat * len_text + (len_pat + len_text)).
