monkerek

# idea: use a 2-D array to mimic set of stacks. 
# use a pivot index to indicate current stack that common pop() and push() are applyed to
# time complexity: O(1)
# space complexity: O(n)

class SetOfStack:
    def __init__(self):
        self.__stack = []
        self.__top = -1

monkerek

# idea: use another stack to store current minimum value each time a new element is pushed in. 
#       pop top values from both 2 stacks when doing pop operation
# time complexity: O(1)
# space complexity: O(n)

class myStack:
    def __init__(self):
        self.__array = []
        self.__min = []
        self.__topIndex = -1

monkerek

# idea: evenly divide an array into 3 parts to implement stacks separately. 
#       use 3 flags to indicate the top index of each stack. check before operation if current stack is full or empty
#       this solution only works for constant length of array
# time complexity: O(1)
# space complexity: O(1) for constant length of array

class myStack:
    def __init__(self):
        self.__array = [-1 for n in range(30)]
        self.__top = [-1, 9, 19]

monkerek

# idea: traverse the string directly and count #characters. Then check whether the result is smaller than input string.
# time complexity: O(n)
# space complexity: O(n)

class Solution:
    def StrCompression(self, string):
        if string == '':
            return string

        ret = ''

monkerek

// first find the index where the actual string ends
// then calculate the number of spaces to be converted to assure the length of the result string
// use two pointers, one pointing to the end of the former string, the other pointing to the end of the result string
// then move pointers backwards to convert spaces one by one, and this can be done in-place.
// time complexity: O(n)
// space complexity: O(1)

class Solution
{
public:

monkerek

# use a dict(hashmap) to count the appearance of characters of the first string, then minus the number of that in the other string.
# once the hash value is less than zero, return false
# time complexity: O(n)
# space complexity: O(1) for certain set of characters, say ascii

class Solution:
  def isPermutation(self, str1, str2):
    if len(str1) != len(str2):
      return False

monkerek

/* idea:    using 2 pointers respectively point to the start and the end of the string, 
            swap the value they point to, then move the pointers iteratively.
   time:    complexity: O(n)
   space    complexity: O(1)
*/

void reverse(char* str)
{
	if(!str)
		return;

monkerek

# idea: sort the string such that same characters sit together, then traverse the string one by one
# time complexity: O(NlogN)? depends on sorting alg.
# space complexity: O(1)


class Solution:
    def UniqueChar(self, string):
        if string == '':
            return True