array / string Flashcards
merge strings alternately
two pointer approach
theory
Create two variables, m and n, to store the length of word1 and word2.
Create an empty string variable result to store the result of merged words.
Create two pointers, i and j to point to indices of word1 and word2. We initialize both of them to 0.
While i < m || j < n:
If i < m, it means that we have not completely traversed word1. As a result, we append word1[i] to result. We increment i to point to next index of word1.
If j < n, it means that we have not completely traversed word2. As a result, we append word2[j] to result. We increment j to point to next index of word2.
Return result.
merge strings alternately
two pointer approach
code
class Solution(object):
def mergeAlternately(self, word1, word2):
m = len(word1)
n = len(word2)
i = 0
j = 0
result = []
while i < m or j < n:
if i < m:
result += word1[i]
i += 1
if j < n:
result += word2[j]
j += 1
return "".join(result)merge strings alternately
approach overview
two approaches:
1) two pointers
2) one pointer
reverse words in a string
approach overview
1) built in split and reverse
2) reverse the whole string and then reverse each word
3) deque of words
reverse words in a string
built in split and reverse code
class Solution:
def reverseWords(self, s: str) -> str:
return “ “.join(reversed(s.split()))
reverse words in a string
reverse string then each word
class Solution:
def trim_spaces(self, s: str) -> list:
left, right = 0, len(s) - 1
# remove leading spaces
while left <= right and s[left] == " ":
left += 1
# remove trailing spaces
while left <= right and s[right] == " ":
right -= 1
# reduce multiple spaces to single one
output = []
while left <= right:
if s[left] != " ":
output.append(s[left])
elif output[-1] != " ":
output.append(s[left])
left += 1
return output
def reverse(self, l: list, left: int, right: int) -> None:
while left < right:
l[left], l[right] = l[right], l[left]
left, right = left + 1, right - 1
def reverse_each_word(self, l: list) -> None:
n = len(l)
start = end = 0
while start < n:
# go to the end of the word
while end < n and l[end] != " ":
end += 1
# reverse the word
self.reverse(l, start, end - 1)
# move to the next word
start = end + 1
end += 1
def reverseWords(self, s: str) -> str:
# converst string to char array
# and trim spaces at the same time
l = self.trim_spaces(s)
# reverse the whole string
self.reverse(l, 0, len(l) - 1)
# reverse each word
self.reverse_each_word(l)
return "".join(l)reverse words in a string
deque of words
def reverseWords(self, s: str) -> str:
left, right = 0, len(s) - 1
# remove leading spaces
while left <= right and s[left] == " ":
left += 1
# remove trailing spaces
while left <= right and s[right] == " ":
right -= 1
d, word = deque(), []
# push word by word in front of deque
while left <= right:
if s[left] == " " and word:
d.appendleft("".join(word))
word = []
elif s[left] != " ":
word.append(s[left])
left += 1
d.appendleft("".join(word))
return " ".join(d)product of array except self (approaches)
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
1) left and right product lists
2) using constant space
product of array except self
code for left and right product lists
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
# The length of the input array
length = len(nums)
# The left and right arrays as described in the algorithm
L, R, answer = [0] * length, [0] * length, [0] * length
# L[i] contains the product of all the elements to the left
# Note: for the element at index '0', there are no elements to the left,
# so the L[0] would be 1
L[0] = 1
for i in range(1, length):
# L[i - 1] already contains the product of elements to the left of 'i - 1'
# Simply multiplying it with nums[i - 1] would give the product of all
# elements to the left of index 'i'
L[i] = nums[i - 1] * L[i - 1]
# R[i] contains the product of all the elements to the right
# Note: for the element at index 'length - 1', there are no elements to the right,
# so the R[length - 1] would be 1
R[length - 1] = 1
for i in reversed(range(length - 1)):
# R[i + 1] already contains the product of elements to the right of 'i + 1'
# Simply multiplying it with nums[i + 1] would give the product of all
# elements to the right of index 'i'
R[i] = nums[i + 1] * R[i + 1]
# Constructing the answer array
for i in range(length):
# For the first element, R[i] would be product except self
# For the last element of the array, product except self would be L[i]
# Else, multiple product of all elements to the left and to the right
answer[i] = L[i] * R[i]
return answerproduct of array except self
describe algorithm for left and right
Initialize two empty arrays, L and R where for a given index i, L[i] would contain the product of all the numbers to the left of i and R[i] would contain the product of all the numbers to the right of i.
We would need two different loops to fill in values for the two arrays.
For the array L, L[0] would be 1 since there are no elements to the left of the first element. For the rest of the elements, we simply use L[i]=L[i−1]∗nums[i−1].
Remember that L[i] represents product of all the elements to the left of element at index i.
For the other array, we do the same thing but in reverse i.e. we start with the initial value of 1 in R[length−1] where length is the number of elements in the array, and keep updating R[i] in reverse.
Essentially, R[i]=R[i+1]∗nums[i+1].
Remember that R[i] represents product of all the elements to the right of element at index i.
Once we have the two arrays set up properly, we simply iterate over the input array one element at a time, and for each element at index i, we find the product except self as L[i]∗R[i].
product of array except self
o(1) space approach
Initialize the empty answer array where for a given index i, answer[i] would contain the product of all the numbers to the left of i.
We construct the answer array the same way we constructed the L array in the previous approach.
These two algorithms are exactly the same except that we are trying to save up on space.
The only change in this approach is that we don’t explicitly build the R array from before. Instead, we simply use a variable to keep track of the running product of elements to the right and we keep updating the answer array by doing
answer[i]=answer[i]∗R. For a given index i, answer[i] contains the product of all the elements to the left and R would contain product of all the elements to the right. We then update R as R=R∗nums[i]
increasing triplet subsequence approaches
Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.
1) linear scan (only listed approach)
increasing triplet subsequence algorithm
Algorithm:
Start with two variables, first_num and second_num, initialized to a large value.
Iterate through the array:
If the current number is smaller than first_num, update first_num.
Else, if it’s smaller than second_num but greater than first_num, update second_num.
If a number is found that’s greater than both first_num and second_num, return True.
If no such triplet is found by the end of the iteration, return False.
increasing triplet subsequence code solution
def increasingTriplet(self, nums: List[int]) -> bool:
first_num = float("inf")
second_num = float("inf")
for n in nums:
if n <= first_num:
first_num = n
elif n <= second_num:
second_num = n
else:
return True
return Falsekids with candies
def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
return [True if (c + extraCandies) >= max(candies) else False for c in candies]greatest common divisor of strings
theory
Suppose there exists a divisible string base, we can write str1 and str2 in the form of multiples of base. Take the following picture as an example.
Since both strings contains multiples of the identical segment base, their concatenation must be consistent, regardless of the order (str1 + str2 = str2 + str1).
Check if the concatenations of str1 and str2 in different orders are the same.
If not, return “”.
Otherwise, get the GCD gcdLength of the two lengths of str1 and str2.
Return the prefix string with a length of gcdLength of either str1 or str2 as the answer.
