import sys
class ListNode(object):
def __init__(self, x=None):
self.val = x
self.next = None
def printLL(node):
while node:
print (node.val, end="->")
node=node.next
def populateLL(array):
node= ListNode(0)
backup=node
for element in array:
node.next=ListNode(element)
node=node.next
return backup.next
Pseudo algorithm for Ordered Dictionary
Can modify this algorithm to suit any type of problem which involves any kind of sliding window or stream processing.
class OrderedDict(object):
def __init__(self,capacity):
self.capacity=capacity
self.head=ListNode("-inf")
self.tail=ListNode("-inf")
self.head.next=self.tail
self.tail.prev=self.head
self.dict={}
def addTail(self,key):
node= ListNode(key)
node.prev= self.tail.prev
node.next=self.tail
self.tail.prev.next=node
self.tail.prev=node
self.dict[key]=node
if len(self.dict)>self.capacity:
self.removeHead()
def removeNode(self,key):
node= self.dict[key]
node.prev.next=node.next
node.next.prev=node.prev
del self.dict[key]
def removeHead(self):
key= self.head.next.val
self.removeNode(key)
obj= OrderedDict(4)
obj.addTail(12)
print(printLL(obj.head))
obj.addTail(13)
obj.addTail(14)
obj.addTail(15)
print(printLL(obj.head))
obj.addTail(16)
print(printLL(obj.head))
obj.removeNode(14)
print(printLL(obj.head))
-inf->12->-inf->None
-inf->12->13->14->15->-inf->None
-inf->13->14->15->16->-inf->None
-inf->13->15->16->-inf->None
In sums where we need to compare two windows, we can create and store the window in either a set
or dict
.
In the example below, we are storing the window in a dict
.
Make sure that the size of widows remain same at all time. Thus del
in the below method.
# 567: Permutation in String On Leetcode
class WindowCompare(object):
def compareWindow(self, s1, s2):
if len(s1)>len(s2):
return False
s1dct = defaultdict(int)
s2dct = defaultdict(int)
for elem in s1:
s1dct[elem]+=1
for i in xrange(len(s1)):
s2dct[s2[i]]+=1
i = 0
for j in xrange(len(s1), len(s2)):
if s1dct == s2dct:
return True
s2dct[s2[j]]+=1
s2dct[s2[i]]-=1
if s2dct[s2[i]]<=0:
del s2dct[s2[i]]
i+=1
if s1dct == s2dct:
return True