LeetCode: Top Interview Problems V

125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

### One Pass: Time - O(n) / Space - O(n)
palindrome = ""
for char in string:
if char.isalnum(): palindrome += char.lower()
return palindrome == palindrome[::-1]

127. Word Ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words such that:

  • The first word in the sequence is beginWord.
  • The last word in the sequence is endWord.
  • Only one letter is different between each adjacent pair of words in the sequence.
  • Every word in the sequence is in wordList.

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

### Breadth First Search: Time - O(n) / Space - O(n**2)
length = len(wordList)
neighbor = {}
for word in wordList + [beginWord]:
for k in range(len(word)):
cloze = word[:k] + "_" + word[k+1:]
if cloze not in neighbor: neighbor[cloze] = []
neighbor[cloze].append(word)
queue, visit = [(beginWord, 1)], []
while queue:
word, step = queue[0]
queue.pop(0)
if word == endWord: return step
if word in visit: continue
visit.append(word)
for k in range(len(word)):
cloze = word[:k] + "_" + word[k+1:]
next_words = neighbor[cloze]
for next_word in next_words:
if next_word in visit: continue
queue.append((next_word, step+1))
return 0

128. Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

Follow up: Could you implement the O(n) solution?

### One Pass: Time - O(n) / Space - O(1)
max_streak = 0
nums = set(nums) # set is much faster for searching
for num in nums:
if num-1 in nums: continue
streak = 1
while num+1 in nums:
num += 1
streak += 1
max_streak = max(max_streak, streak)
return max_streak

130. Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

### Depth First Search: Time - O(n**2) / Space - O(1)
if board == []: return 0
length = [len(board), len(board[0])]
def mark(pos):
if board[pos[0]][pos[1]] != "O": return
board[pos[0]][pos[1]] = "#"
direction = [(0,1), (1,0), (0,-1), (-1,0)]
for k in range(4):
if not 0 <= pos[0] + direction[k][0] < length[0]: continue
if not 0 <= pos[1] + direction[k][1] < length[1]: continue
mark((pos[0] + direction[k][0], pos[1] + direction[k][1]))
return
for i in range(length[0]):
mark((i,0))
mark((i,length[1]-1))
for j in range(length[1]):
mark((0,j))
mark((length[0]-1,j))
for i in range(length[0]):
for j in range(length[1]):
if board[i][j] == "O": board[i][j] = "X"
for i in range(length[0]):
for j in range(length[1]):
if board[i][j] == "#": board[i][j] = "O"
return

131. Palindrome Partitioning

Given a string string, partition string such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of string.

A palindrome string is a string that reads the same backward as forward.

### Depth First Search: Time - O(n 2**n) / Space - O(n)
### can combine dynamic programming
length = len(string)
if length == 0: return [[]]
if length == 1: return [[string]]
result = []
for k in range(1, length):
if string[:k] != string[:k][::-1]: continue
left_results = self.partition(string[k:])
for left_result in left_results:
result.append([string[:k]] + left_result)
if string == string[::-1]: result.append([string])
return result

134. Gas Station

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ithstation to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

### Brute Force: Time - O(n**2) / Space - O(1)
length = len(gas)
for start in range(length):
total = 0
for current in range(start, start + length):
total += gas[current%length] - cost[current%length]
if total < 0: break
### reduce time complexity to O(n)
# if total < 0: start = current % length; break
if total >= 0: return start
return -1

136. Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

### HashTable: Time - O(n) / Space - O(n)
dic = {}
for num in nums:
if num not in dic: dic[num] = 0
dic[num] += 1
for num in dic:
if dic[num] == 1: return num
### Bitwise Operation: Time - O(n) / Space - O(1)
result = 0
for num in nums:
result = result ^ num
return result

138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.
### Two Passes: Time - O(n) / Space - O(n)
nodes = {}
tail = head
while tail:
nodes[tail] = Node(tail.val)
tail = tail.next
tail = head
while tail:
nodes[tail].next = nodes[tail.next] if tail.next else None
nodes[tail].random = nodes[tail.random] if tail.random else None
### use get to deal with "None"
# nodes[tail].next = nodes.get(tail.next)
# nodes[tail].random = nodes.get(tail.random)
tail = tail.next
return nodes.get(head)

139. Word Break

Given a non-empty string string and a dictionary wordDict containing a list of non-empty words, determine if string can be segmented into a space-separated sequence of one or more dictionary words.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.
### Recursion: Time - O(nlogn) / Space - O(1)
if len(string) == 0: return True
result = False
for word in wordDict:
if not string.startswith(word): continue
result = result | self.wordBreak(string[len(word):], wordDict)
if result == True: return True
return result
### Dynamic Programming: Time - O(n) / Space - O(n)
length = len(string)
result = [True]
for k in range(1, length+1):
result.append(False)
for word in wordDict:
if k-len(word) < 0: continue
if not string[k-len(word):].startswith(word): continue
if not result[k-len(word)]: continue
result[k] = True
return result[length]

140. Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.
### Recursion: Time - O(nklogn) / Space - O(nk)
if len(string) == 0: return [""]
result = []
for word in wordDict:
if not string.startswith(word): continue
tmp_results = self.wordBreak(string[len(word):], wordDict)
for tmp_result in tmp_results:
if tmp_result == "": result.append(word)
if tmp_result != "": result.append(word + " " + tmp_result)
return result
### Dynamic Programming: Time - O(nk) / Space - O(nk)
length = len(string)
exists = [True]
for k in range(1, length+1):
exists.append(False)
for word in wordDict:
if k-len(word) < 0: continue
if not string[k-len(word):].startswith(word): continue
if not exists[k-len(word)]: continue
exists[k] = True
if exists[length] == False: return []
result = [[""]]
for k in range(1, length+1):
result.append([])
if exists[k] == False: continue
for word in wordDict:
if k-len(word) < 0: continue
if exists[k-len(word)] == False: continue
if not string[k-len(word):].startswith(word): continue
for prev in result[k-len(word)]:
if prev == "": result[k].append(word)
if prev != "": result[k].append(prev+ " " + word)
return result[length]

141. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

### Cycle Finding: Time - O(n) / Space - O(1)
if head is None: return False
slow = head
fast = head.next
while slow != fast:
if fast is None or fast.next is None: return False
slow = slow.next
fast = fast.next.next
return True

148. Sort List

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

### MergeSort: Time - O(nlogn) / Space - O(logn)
if head is None: return head
if head.next is None: return head
slow = head
fast = head
while slow and fast:
if fast.next is None: break
if fast.next.next is None: break
slow = slow.next
fast = fast.next.next
half = slow.next
slow.next = None
l1 = self.sortList(head)
l2 = self.sortList(half)
merge_head = ListNode()
merge_tail = merge_head
while l1 and l2:
if l1.val <= l2.val: merge_tail.next = l1; l1 = l1.next
elif l1.val >= l2.val: merge_tail.next = l2; l2 = l2.next
merge_tail = merge_tail.next
if l1: merge_tail.next = l1
if l2: merge_tail.next = l2
# merge_tail = l1 or l2
return merge_head.next

149. Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.