Dutch Flag problem

Dutch flag is a notable problem wherein you have a array representing three colors . Red(R), Green(G) and Blue(B) which needs to be sorted with Reds coming first followed by Green and then Blue. This is achieved by lumoto partitioning scheme.

	arr = ['G','B','R','G','B','G','R']
	ridx=0
	bidx=len(arr)-1
	i=0
	while(i<bidx):
	if(arr[i] == 'R'):
	arr[i],arr[ridx] = arr[ridx],arr[i]
	ridx += 1
	i = i+1
	elif (arr[i] == 'B'):
	arr[i],arr[bidx] = arr[bidx], arr[i]
	bidx -= 1
	else:
	i=i+1
	print(arr)

view raw dutchflag.py hosted with ❤ by GitHub

Printing out all combinations of string

Printing out all combinations of a string

	#! /bin/env/path python
	def printCombinations(slate,array):
	if (len(array)==0):
	print(slate)
	return
	printCombinations(slate,array[1:])
	printCombinations(slate+array[0], array[1:])
	printCombinations("", "abcd")

view raw Combinations.py hosted with ❤ by GitHub

Printing out all the permutations of string

How to generate permutation of a given string where digits are kept as it is, but alphabets are replaced by lower and upper case characters

	#! /usr/env/path python
	def helper(string, result, index , slate):
	if (len(string) == len(slate)):
	result.append(slate)
	return
	if(string[index].isdigit()):
	slate = slate + str(string[index])
	helper(string, result, index+1, slate)
	slate = slate[:-1]
	else:
	slate= slate + str(string[index].upper());
	helper(string, result, index+1, slate)
	slate = slate[:-1]
	slate = slate + str(string[index].lower())
	helper( string, result, index+1, slate)
	result =[]
	helper("a1b2",result, 0 , "")
	print(result)

view raw letterPermutationSort.py hosted with ❤ by GitHub

The above solution uses immutable strings so its not efficient time complexity-wise below solution replaces string with list

	#! /usr/env/path python
	''' This solution is done using list and removes the immutable
	string to avoid extra burden on time '''
	def solutions():
	result=[]
	def helper(index,slate=None):
	if slate== None:
	slate=[]
	if len(slate) == bag_len:
	result.append(''.join(slate))
	return
	if(bag[index].isdigit()):
	slate.append(bag[index])
	helper(index+1, slate)
	slate.pop()
	else:
	slate.append(str(bag[index].upper()))
	helper(index+1,slate)
	slate.pop()
	slate.append(str(bag[index].lower()))
	helper(index+1, slate)
	slate.pop()
	slate1 = list()
	bag = list("a1b2c3")
	bag_len = len(bag)
	helper( 0, slate1)
	print(result)
	solutions()

view raw strinnum.py hosted with ❤ by GitHub

Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome. 

 Example 1: Input: head = [1,2,2,1] 

Output: true 

Example 2: Input: head = [1,2]

 Output: false 

 Constraints: The number of nodes in the list is in the range [1, 105]. 0 <= Node.val <= 9 

 Follow up: Could you do it in O(n) time and O(1) space?

	from collections import deque
	# 1->2->3->4->4->3->2->1
	# b b b b
	# f f f b
	# 1->2->3->4->5->4->3->2->1
	# b b b b b
	# f f f f f
	# Definition for singly-linked list.
	# class ListNode:
	# def __init__(self, val=0, next=None):
	# self.val = val
	# self.next = next
	class Solution:
	arr = []
	def isPalindrome(self, head: ListNode) -> bool:
	stack = deque()
	if (head == None):
	return False
	if (head.next == None):
	return True
	back = head
	front = head
	if(head.next.next == None):
	if(head.val == head.next.val):
	return True
	else:
	return False
	#store all values till mid in linked list to a stack
	while (front.next != None and front.next.next != None):
	stack.append(back.val)
	back = back.next
	front = front.next.next
	if(front.next == None):
	back = back.next
	else:
	temp = back.val
	if(back.next.val != temp):
	return False
	back = back.next.next
	while (back != None):
	poppedval = stack.pop()
	if back.val != poppedval :
	return False
	back = back.next
	return True

view raw palindrom_linkedlist.py hosted with ❤ by GitHub