Sunday, April 21, 2019

Leetcode solution 10: Regular Expression Matching

Problem Statement 

Given an input string (s) and a pattern (p), 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).
Note:
  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

The thought process is very similar to Leetcode Solution 44: Wildcard Matching, you can find the blog here and the video tutorial here.

Step 0 really is to understand what the "*" really means.
'*' Matches zero or more of the preceding element.
A few examples,
  • "" and "a*": True, since * could match zero occurrence of the preceding char 'a', not here zero means deleting the original 'a'
  •  "a" and "a*": True, since * could match "one" occurrence in total
  • "aa" and "a*": True since * could match an extra one occurrence of the preceding char 'a', you can also think of it as "two" occurrences of 'a' in total
  • "" and "*": A very tricky case, my code below returns True but leetcode expects False. My code still passes OJ so this is really not a valid case. I argue this should be True since it is one occurrence of empty "" in total

The first attempt (if you haven't seen this question before) is trying to solve it using recursion. The idea is simple. While comparing the s and p char by char, as soon as you see a "*", you will start recurse
  • remove the preceding char and the "*", recurse and compare 
  • for every char equals to the preceding char in the pattern, as long as they are equal to the current char in s, recurse and compare
The time complexity in a ballpark looks like exponential to the P length, but a more detailed analysis from leetcode's original solution can be found here.

If you recall what problems can be solved using DP, DP (Dynamic Programming) is normally a great way when trying to answer below two types of questions, and string related questions are a majority use case of DP
  • Only Yes/No, True/False question without returning detailed step by step results 
  • Extreme values, e.g., Max, Min, Best optimal value
 I have posted several videos on how to solve DP problems using a template, essentially
  1. Initialize your lookup array, could be 2 dimensional or 1 dimensional using rolling arrays
  2. Initialize the init values in your array
  3. Get the math formula for a[i] = a[i-1] * m - n or whatever condition you need
  4. Code it up
This problem can be solved using DP by having formulas like below when a "*" is seen


Once you have the formula, coding up DP problem should be a piece of cake. You can find the video tutorial on this problem here

Solutions

DP solution

Time Complexity: assuming S length is M, P length is N, this is O(M*N) because all we need to do is build up that lookup matrix
Space Complexity: assuming S length is M, P length is N, this is O(M*N), again, that lookup matrix

References

Sunday, April 14, 2019

Leetcode solution 44: Wildcard Matching

Problem Statement 

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Note:
  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like ? or *.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:
Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:
Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:
Input:
s = "acdcb"
p = "a*c?b"
Output: false
Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

It seems an easy problem first using recursion and brute forcefully solving the problem, but the OJ will quickly throw a TLE (Time Limit Exceeded) error since it is exponential time. Well, if you were like me, tried really hard to optimize my brute force solution, either using some heuristics or pruning on the recursion, however, still no luck :(

DP (Dynamic Programming) is normally a great way when trying to answer below two types of questions, and string related questions are a majority use case of DP
  • Only Yes/No, True/False question without returning detailed step by step results 
  • Extreme values, e.g., Max, Min, Best optimal value
 I have posted several videos on how to solve DP problems using a template, essentially
  1. Initialize your lookup array, could be 2 dimensional or 1 dimensional using rolling arrays
  2. Initialize the init values in your array
  3. Get the math formula for a[i] = a[i-1] * m - n or whatever condition you need
  4. Code it up 
You can find the video tutorial on this problem here

Solutions

Brute force recursion, TLE

Time Complexity: assuming S length is M, P length is N, this is O(M*2^N), exponential basically
Space Complexity: No extra space needed other than the additional recursion function stack

 


DP solution

Time Complexity: assuming S length is M, P length is N, this is O(M*N) because all we need to do is build up that lookup matrix
Space Complexity: assuming S length is M, P length is N, this is O(M*N), again, that lookup matrix

References

Monday, April 1, 2019

Leetcode solution 208: Implement Trie (Prefix Tree)

Problem Statement 

Implement a trie with insertsearch, and startsWith methods.
Example:
Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true
Note:
  • You may assume that all inputs are consist of lowercase letters a-z.
  • All inputs are guaranteed to be non-empty strings.
Problem link

Video Tutorial

You can find the detailed video tutorial here


Thought Process

Trie (prefix tree) is a very common data structure that appears very often in interviews. I used to get asked Trie at Fitbit, Snap and Google back in the days. I highly recommend you brush up on this basic data structure.

Please refer to this Baozi Training Blog for a modified version explained:
https://blog.baozitraining.org/2019/03/leetcode-solution-211-add-and-search.html

Leetcode actually did a great job explaining this problem. Feel free to download the explanation here (all credit and copyright goes to leetcode, obviously) 

Solutions

 


Time Complexity: assuming N is the word length, insert O(N), search O(N), startWith O(N)
Space Complexity: assuming N is the word length, insert O(N), search O(1), startWith O(1)

References