Leetcode

This is my solution to Leetcode Online Judge's problems. Currently I am revamping the problems all over again towards more idiomatic Python. Stay tuned for updates.

Feel free to submit pull requests for submitting more elegant solution.

###List of idiomatic Python I prefer (as of now)

• Prefer list comprehension over map / filter.

	# from Gray Code
# Bad
def grayCode(self, n):
return map(lambda x: (x / 2) ^ x, range(1 << n))
# Idiomatic
def grayCode(self, n):
return [(x / 2) ^ x for x in range(1 << n)]

• Prefer using in keyword over repetitive variable in conditional statement.

	# from Post Order Traversal
# Bad
if parent.right == None or parent.right == prev
# Idiomatic
if parent.right in (None, prev):

• Prefer using docstring over single line comment when describing functionality of a method.

	# from Search Insert Position
# Bad
# Iterative solution is also fine.
def searchInsert(self, A, target):
# Idiomatic
def searchInsert(self, A, target):
"""Iterative solution is also fine.
"""

• Prefer implicit evaluation of condition (e.g. if, while, etc.) over explicit comparison in condition.
  Notice empty list and dictionary will be evaluated to False, so that is very handy.

	# from Binary Tree Preorder Traversal
# Bad
while len(stack) > 0:
current = stack.pop()
# Idiomatic
while stack:
current = stack.pop()

• Prefer is None over == None. Notice is looks for referential equality, and None is a singleton.
  The fundamental reason for this preference is much improved speed, and == can be overriden by __eq__.

	# from Binary Tree Preorder Traversal
# Bad
if root == None:
# Idiomatic
if root is None:

One interesting side note in Python regarding this is on Stackoverflow. Trust me, that is worth your 60 seconds of time. But that only works in REPL though, not on a executable python file.

READ THIS or above two rules will only do you harm:
Sometimes you have to use if foo is not None over if foo. For example, if foo is 0, then if foo will become False. But 0 is not None. Just watch out. A rule of the thumb is if you want to check if the default argument of a function is None, then use if foo is not None, otherwise you can most likely use if foo if you know what you are doing.

• Consider using enumerate when index accessing looks verbose

	# from Two Sum
# Bad
for i in range(len(nums)):
if target - nums[i] in lookup:
return (lookup[target - nums[i]] + 1, i + 1)
lookup[nums[i]] = i
# Idiomatic
for i, num in enumerate(nums):
if target - num in lookup:
return (lookup[target - num] + 1, i + 1)
lookup[num] = i

• Readability counts.

"Any fool can write code that a computer can understand. Good programmers write code that humans can understand." Martin Fowler is right.

	# from Edit Distance
# Bad
def minDistance(self, word1, word2):
distance = [[i] for i in range(len(word1) + 1)]
distance[0] = [i for i in range(len(word2) + 1)]
for i in range(1, len(word1) + 1):
for j in range(1, len(word2) + 1):
distance[i].append(min(distance[i - 1][j] + 1, distance[i][j - 1] + 1, distance[i - 1][j - 1] + (word1[i - 1] != word2[j - 1])))
return distance[-1][-1]
# Idiomatic
def minDistance(self, word1, word2):
distance = [[i] for i in range(len(word1) + 1)]
distance[0] = [i for i in range(len(word2) + 1)]
for i in range(1, len(word1) + 1):
for j in range(1, len(word2) + 1):
deletion = distance[i - 1][j] + 1
addition = distance[i][j - 1] + 1
substitution = distance[i - 1][j - 1]
if word1[i - 1] != word2[j - 1]:
substitution += 1
distance[i].append(min(deletion, addition, substitution))
return distance[-1][-1]