Created
February 21, 2021 09:06
-
-
Save samarthsewlani/09a78f300c840a860e78a0aee297ad26 to your computer and use it in GitHub Desktop.
Super Reduced String HackerRank Solution ( Better logic )
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node: #Definition of Node class | |
def __init__(self,value,previous): | |
self.value=value | |
self.next=None | |
self.prev=previous | |
def __str__(self): | |
return "Node {}".format(self.value) | |
def superReducedString(s): | |
head=Node("#",None) #Initialize head node with some different value | |
length=len(s) | |
current=head | |
for i in range(0,length): | |
current.next=Node(s[i],current) #Keep on linking the nodes and make the doubly linked list | |
current=current.next | |
current=head | |
while current!=None: | |
if current.next==None: #If there is no next node simply break out of loop | |
break | |
if current.value==current.next.value: #If value of adjacent nodes are equal | |
previous=current.prev #Store the reference to the previous node | |
previous.next=current.next.next #Link the <previous node's next> to <next to next node of current> | |
if current.next.next!=None: #Taking care of corner case (if next to next node is None it will not have prev attribute and result into Error) | |
current.next.next.prev=previous #Link the <prev of next to next node of current> to <prev of current> | |
current=previous # Go back one node(to check whether it matches with the next node after the above operations) | |
else: | |
current=current.next #If values are not equal simply go ahead one node | |
current=head.next | |
if head.next==None: #If there is nothing in the linked list | |
print("Empty String") | |
return | |
while current!=None: | |
print(current.value,end=””) | |
current=current.next | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment