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
# 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 |
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
# 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 |
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
# 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] |
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
# 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 = '' |
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
# 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 |
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
// 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: |
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
# 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 |
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
/* 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; |