A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
# Time complexity: O(n)# Space complexity: O(1)defisPalindrome(s:str)->bool: start =0 end =len(s)-1 s = s.lower()while start < end:ifnot s[start].isalnum(): start +=1elifnot s[end].isalnum(): end -=1elif s[start]== s[end]: start +=1 end -=1else:returnFalsereturnTrue
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).
# Time complexity: O(n)# Space complexity: O(1)defisSubsequence(s:str, t:str)->bool: si = ti =0while si <len(s)and ti <len(t):if s[si]== t[ti]: si +=1 ti +=1return si ==len(s)
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
Assume there is exactly one solution. Do not use the same element twice. The solution must use only constant extra space.
# Time complexity: O(n)# Space complexity: O(1)deftwoSum(numbers: List[int], target:int)-> List[int]: start, end =0,len(numbers)-1while start < end: currSum = numbers[start]+ numbers[end]if currSum == target:return[start +1, end +1]if currSum < target: start +=1else: end -=1
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
# Time complexity: O(n)# Space complexity: O(1)defmaxArea(height: List[int])->int: start, end =0,len(height)-1 answer =0while start < end: answer =max(answer,(end - start)*min(height[start], height[end]))# Keep the pointer with a greater valueif height[start]< height[end]: start +=1# In the case of height[start] == height[end],# the pointer to move does not matter because# regardless of the next pointer's value,# the calculated area will never be greater.else: end -=1return answer
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
The solution set must not contain duplicate triplets.
# Time complexity: O(n^2)# Space complexity: O(n)defthreeSum(nums: List[int])-> List[List[int]]: answer =set() nums.sort() i =0# Essentially 2Sum with an extra loop and dynamic targetwhile i <len(nums): target =-1* nums[i] start, end = i +1,len(nums)-1while start < end: currSum = nums[start]+ nums[end]if currSum > target: end -=1elif currSum < target: start +=1else: triplet =tuple(sorted([nums[i], nums[start], nums[end]])) answer.add(triplet)# Skip duplicates from front and backwhile start < end and nums[start]== triplet[1]: start +=1while start < end and nums[end]== triplet[2]: end -=1# Skip duplicates of current integerwhile i +1<len(nums)and nums[i +1]== nums[i]: i +=1 i +=1return answer