Tag: leetcode-medium

Another Solution: Longest Palindrome Substring

class Solution(object): def __init__(self): self.lookup = {“test”} def isPalindrome(self, s, i, k): j = i + k – 1 if s[i] == s[j]: key = self.createKey(i + 1, j – 1) if key in self.lookup: #self.lookup.remove(key) return True return False def createKey(self, i, j): #return “{}:{}”.format(i,j) #return (i, j) #key = bin(i) + bin(j) #return…

Longest Palindrome Substring in a String

DP based solution class Solution(object): def __init__(self): self.lookup = {} def isPalindrome(self, s, dp, i, k): j = i + k – 1 if s[i] == s[j] and dp[i + 1][j – 1]: return True return False def longestPalindrome(self, s): “”” :type s: str :rtype: str “”” size = len(s) if size < 2: return…

Union-Find Problem

The problem is to find if a given edge (a, b) is connected in a graph with vertices {a, b, c, …}. Naive Solution – O(n^2) Maintain a parent array of size (len of vertex array) Update an edge (a, b) with the index a & b in the vertex array ParentArray[a] = b ParentArray[b]…

Longest Substring without Repeating Characters

The solution uses a sliding window and uses O(n) time and O(n) space. There are many cases to take care of. We can skip the process string less than size 2. Iterate the string, checking each char as key in the hash, adding if not present. If not present in hash, add each char as…

Adding Two Numbers in LinkedList

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def addTwoNumbers(self, l1, l2): “”” :type l1: ListNode :type l2: ListNode :rtype: ListNode “”” head1, head2 = l1, l2 head3 = None last = head3 carry = 0 while head1 and head2: dsum…