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!

Python
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).