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).

Create your website at WordPress.com
Get started