# 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]))

returnfor 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 `ith`

station 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] += 1for 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.nexttail = 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 Trueresult = 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 Falseslow = 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 headslow = 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.nexthalf = slow.next

slow.next = Nonel1 = 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.