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

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    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 = 0nums = set(nums)    # set is much faster for searchingfor 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 0length = [len(board), len(board)]def mark(pos):    if board[pos][pos] != "O": return    board[pos][pos] = "#"    direction = [(0,1), (1,0), (0,-1), (-1,0)]    for k in range(4):        if not 0 <= pos + direction[k] < length: continue        if not 0 <= pos + direction[k] < length: continue        mark((pos + direction[k], pos + direction[k]))    returnfor i in range(length):    mark((i,0))    mark((i,length-1))for j in range(length):    mark((0,j))    mark((length-1,j))for i in range(length):    for j in range(length):        if board[i][j] == "O": board[i][j] = "X"for i in range(length):    for j in range(length):        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 programminglength = 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 startreturn -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 = 0for num in nums:    result = result ^ numreturn 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 = headwhile tail:    nodes[tail] = Node(tail.val)    tail = tail.nexttail = headwhile 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.nextreturn 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 = Falsefor word in wordDict:    if not string.startswith(word): continue    result = result | self.wordBreak(string[len(word):], wordDict)    if result == True: return Truereturn 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] = Truereturn 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] = Trueif 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]`

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 = headfast = head.nextwhile slow != fast:    if fast is None or fast.next is None: return False    slow = slow.next    fast = fast.next.nextreturn 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 headif head.next is None: return headslow = headfast = headwhile slow and fast:    if fast.next      is None: break    if fast.next.next is None: break    slow = slow.next    fast = fast.next.nexthalf = slow.nextslow.next = Nonel1 = self.sortList(head)l2 = self.sortList(half)merge_head = ListNode()merge_tail = merge_headwhile 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.nextif l1: merge_tail.next = l1if l2: merge_tail.next = l2# merge_tail = l1 or l2return 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.

## More from Tseng1026

BS in Computer Science, National Taiwan University (NTU); MS in Artificial Intelligence, National University of Singapore (NUS)