## LeetCode 20 – Python 3 (Week 1 – 02)

Solution 1 (Runtime: 40 ms Memory Usage: 13.9 MB)

```Tclass Solution:
def isValid(self, s: str) -> bool:
#The last character should be the corresponding bracket of the first character, thus, we can use stack.
#One open bracket must be closed by the same type of close bracket. So, we can use dictionary.

stack = []
bracket = {'(':')', '{': '}', '[' : ']'}

for parenthes in s:
if parenthes in bracket:
stack.append(parenthes)

elif len(stack) == 0 or parenthes != bracket[stack.pop()]: #parenthes != bracket[stack.pop()] or len(stack) == 0 is not right
return False

return len(stack) == 0 #All open brackets have same type of close brackets.
```

Time complexity is O(n). Space complexity is O(n).

## LeetCode 1 – Python 3 (Week 1 – 01)

Solution 1 (Runtime: 1288 ms Memory Usage: 14.6 MB)

```class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:

for i in nums:
j = target - i
indice_1 = nums.index(i)
indice_2 = indice_1 + 1
tmp_nums = nums[indice_2: ] # you may not use the same element twice
if j in tmp_nums:
return(indice_1, tmp_nums.index(j)+indice_2) # not use nums.index(j) because 'you may not use the same element twice'
```

Solution 2 (Runtime: 60 ms Memory Usage: 15.2 MB)

```class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:

numspool = {} #dictionary

for i in range(len(nums)):
if target - nums[i] not in numspool:
numspool[nums[i]] = i
else:
return(numspool[target - nums[i]], i)
```

Time complexity of solution 1 is O(n*n). Time complexity of solution 2 is O(n). Because dictionary offer O(1) lookup time. Space complexities of both of them are O(n).