Longest Palindromic Substring
5. Longest Palindromic Substring
Solution
Similar to 647. Palindromic Substrings
Maximum Product Subarray
152. Maximum Product Subarray
Solution
Only when the num is 0, we are sure to restart.
Choose the even number of negative nums from left and right, compare them.
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = nums[0]
curr = 1
for num in nums:
curr = curr...
LRU Cache
146. LRU Cache
Solution - OrderedDict
[Reference](https://leetcode.com/problems/lru-cache/discuss/45952/Python-concise-solution-with-comments-(Using-OrderedDict)
OrderedDict = doubly linked list + hash map
Update chache when get.
If key is in dic when set, we don’t need to update remain, i.e. it’s not consuming capacity.
Add Two Numbers
2. Add Two Numbers
Solution
Need to keep pre and check if pre is 0 at the end.
Cleaner Solution
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
res = ListNode(0)
tail = res
pre = 0
while l1 or l2:
val = pre
if l1:
val += l1.val
l1 = l1.next
if l2:
...
Word Search
79. Word Search
Solution
Reference
Check if we can find the word starting at any postion [i,j].
We should NOT visit visited grid again.
Reset the visited grid when a new loop start.
```python
def exist(self, board, word):
if not board:
return False
for i in xrange(len(board)):
for j in xrange(len(board[0])...
Search in Rotated Sorted Array
33. Search in Rotated Sorted Array
Solution - Modified Binary Search
In this case we cannot ‘throw away’ half of the array like in binary search, because the array is rotated.
We try if the 1st half of the array works, if it works, we’re done, otherwise try with another half.
```python
def search(self, nums, target):
“””
:typ...
Find First and Last Position of Element in Sorted Array
34. Find First and Last Position of Element in Sorted Array
Solution 1 - Use Library
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if len(nums) == 0:
return [-1, -1]
l, r = min(len(nums) - 1, bisect.bisect_left(nums, target)), bisect.bisect_right(nums, t...
199 post articles, 25 pages.