# [Leetcode] 10. Regular Expression Matching

I came across an interesting leetcode problem and decided to solve it in Python (a language I’m not comfortable with) for practice.

Here’s the problem:

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

This problem reminded me of an incredible article I read a long time ago. I admit that I drew inspiration from it when solving this question, and writing my code.

The trick is make the pattern compact so for example, we shorten “a*.*” and “a*a*” into “.*” and “a*”

In Python, we can somewhat brute-force this by comparing lengths and adding/reducing “*” and “.*” segments.

We divide it up, compare characters and lengths, and keep matching substrings, etc. (once yousee the code it’ll be more clear)

Overall, the problem is a matter of checking every case, utilizing DFS, and making sure all the cases are covered.

I truly hope this does not appear in any software engineer interview as it was very challenging, at least for me.

If you know a better way to solve this, please let me know!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
class Solution: def _compile(self, p): answer = '' while len(p) != 0: if len(p) >= 2 and p[1] == '*': if len(answer) < 2 or answer[-1] != '*': result += p[0:2] elif answer[-2] == p[0] or answer[-2] == '.': pass elif p[0] == '.': while len(answer) >= 2 and answer[-1] == '*': answer= answer[:-2] answer+= p[:2] else: answer+= p[0:2] p = p[2:] else: answer+= p[0] p = p[1:] return answer def _isMatch(self, s, p): if len(s) == 0 and len(p) == 0: return True elif len(p) == 0: return False elif len(p) >= 2 and p[1] == '*': return self._isMatchStartRegex(s, p[2:], p[0]) elif len(s) == 0: return False elif s[0] == p[0] or p[0] == '.': return self._isMatch(s[1:], p[1:]) else: return False def _isMatchStartRegex( self, s, p, ch, ): # DFS while True: # skip the * segment. if self._isMatch(s, p): return True elif len(s) == 0: # nothing left. return False elif s[0] == ch or ch == '.': # one! s = s[1:] else: return False def isMatch(self, s, p): assert p == '' or p[0] != '*' return self._isMatch(s, self._compile(p)) |

I apologize in advance if my coding-style is bad. Python is one of my weaker languages and the purpose of doing this problem was to learn.

Obviously, I didn’t read up on detailed styling guides so I just used the automatic formatting feature but I’m unsure if that’s even working properly because it looks kind of off (maybe I’m just so used to Java haha).