Levenshtein Distance Code Structure

J. David Martinez

J. David Martinez

Open DS&A Founder

I believe the code for the levenshtein minimum edit distance is much more readable in this fashion, albeit not following PEP 8 style guide and using two extra variables.

Solution 1:

def levenshteinDistance(str1, str2):
# Create empty string row
edits_table = [[x for x in range(len(str1) + 1)] for y in range(len(str2) + 1)]
# Create empty string column
for row in range(1, len(str2) + 1):
edits_table[row][0] = edits_table[row - 1][0] + 1
# Main algorithm
for row in range(1, len(str2) + 1):
for col in range(1, len(str1) + 1):
# Extra variables to make work being done in string more clear
i = row
j = col
if str2[i - 1] == str1[j - 1]:
edits_table[row][col] = edits_table[row - 1][col - 1]
else:
edits_table[row][col] = 1 + min(edits_table[row - 1][col], edits_table[row - 1][col - 1], edits_table[row][col - 1])
return edits_table[-1][-1]

Solution 2:

def levenshteinDistance(str1, str2):
# Find small and big strings
small = str1 if len(str1) < len(str2) else str2
big = str1 if len(str1) >= len(str2) else str2
# Create even and odd edit table rows
even_edits = [x for x in range(len(small) + 1)]
odd_edits = [None for x in range(len(small) + 1)]
# Main algorithm
for row in range(1, len(big) + 1):
# Extra variable to make value of beginning of current edits row clear
i = row
# Swap current and previous edit rows
if row % 2 == 1:
current_edits = odd_edits
previous_edits = even_edits
else:
current_edits = even_edits
previous_edits = odd_edits
current_edits[0] = i
for col in range(1, len(small) + 1):
# Extra variable to make work being done in string more clear
j = col
if big[i - 1] == small[j - 1]:
current_edits[col] = previous_edits[col - 1]
else:
current_edits[col] = 1 + min(current_edits[col - 1], previous_edits[col - 1], previous_edits[col])
return even_edits[-1] if len(big) % 2 == 0 else odd_edits[-1]

I hope this helps! I learned so much solving this problem 🧠.

Min Height BST Code Structure

J. David Martinez

J. David Martinez

Open DS&A Founder

I think separating out the logic for all 3 solutions makes the code more understandable, even though it's not following the PEP 8 style guide.

Solution 1:

def minHeightBst(array):
return constructMinHeightBST(array, None, 0, len(array) - 1)
def constructMinHeightBST(array, bst, start_index, end_index):
# Once start index reaches end index
if start_index > end_index:
return
middle_index = (start_index + end_index) // 2
value_to_add = array[middle_index]
if bst is None:
bst = BST(value_to_add)
else:
bst.insert(value_to_add)
constructMinHeightBST(array, bst, start_index, middle_index - 1)
constructMinHeightBST(array, bst, middle_index + 1, end_index)
return bst
class BST:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(self, value):
if value < self.value:
if self.left is None:
self.left = BST(value)
else:
self.left.insert(value)
else:
if self.right is None:
self.right = BST(value)
else:
self.right.insert(value)

Solution 2:

def minHeightBst(array):
return constructMinHeightBST(array, None, 0, len(array) - 1)
def constructMinHeightBST(array, bst, start_index, end_index):
# Once start index reaches end index
if start_index > end_index:
return
middle_index = (start_index + end_index) // 2
newBstNode = BST(array[middle_index])
if bst is None:
bst = newBstNode
else:
if array[middle_index] < bst.value:
bst.left = newBstNode
bst = bst.left
else:
bst.right = newBstNode
bst = bst.right
constructMinHeightBST(array, bst, start_index, middle_index - 1)
constructMinHeightBST(array, bst, middle_index + 1, end_index)
return bst
class BST:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

Solution 3:

def minHeightBst(array):
return constructMinHeightBST(array, 0, len(array) - 1)
def constructMinHeightBST(array, start_index, end_index):
# Once start index reaches end index
if start_index > end_index:
return None
middle_index = (start_index + end_index) // 2
bst = BST(array[middle_index])
bst.left = constructMinHeightBST(array, start_index, middle_index - 1)
bst.right = constructMinHeightBST(array, middle_index + 1, end_index)
return bst
class BST:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

I hope this helps! I want to keep best practices in the documentation, thus this seperate blog post 👍.

Smallest Difference Code Structure

J. David Martinez

J. David Martinez

Open DS&A Founder

Here, I think the smallest difference code is more readable but, it might not be following best practices:

def smallestDifference(arrayOne, arrayTwo):
arrayOne.sort()
arrayTwo.sort()
ptrOne = 0
ptrTwo = 0
smallest = float("inf")
current_difference = float("inf")
while ptrOne < len(arrayOne) and ptrTwo < len(arrayTwo):
x = arrayOne[ptrOne]
y = arrayTwo[ptrTwo]
if x < y:
current_difference = y - x
ptrOne += 1
elif y < x:
current_difference = x - y
ptrTwo += 1
else:
return [x, y]
if current_difference < smallest:
smallest = current_difference
smallest_pair = [x, y]
return smallest_pair

This is just my honest opinion 🙂.

Node Depths Code Structure

J. David Martinez

J. David Martinez

Open DS&A Founder

Honestly, I think that the node depths code should look like this:

def nodeDepths(root):
sumOfDepths = 0
stack = [{
"node": root,
"depth": 0
}]
while len(stack) > 0:
obj = stack.pop()
node = obj["node"]
depth = obj["depth"]
#node, depth = obj["node"], obj["depth"]
if node is None:
continue
sumOfDepths += depth
stack.append({"node": node.left, "depth": depth + 1})
stack.append({"node": node.right, "depth": depth + 1})
return sumOfDepths
class BinaryTree:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

It's much more appealing to the eyes, and it shows the different parts of the algorithm.