Huahua’s Tech Road

花花酱 LeetCode 1662. Check If Two String Arrays are Equivalent

By zxi on November 22, 2020

Given two string arrays word1 and word2, returntrue if the two arrays represent the same string, and false otherwise.

A string is represented by an array if the array elements concatenated in order forms the string.

Example 1:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

Example 2:

Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false

Example 3:

Input: word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true

Constraints:

1 <= word1.length, word2.length <= 10³
1 <= word1[i].length, word2[i].length <= 10³
1 <= sum(word1[i].length), sum(word2[i].length) <= 10³
word1[i] and word2[i] consist of lowercase letters.

Solution1: Construct the string

Time complexity: O(l1 + l2)
Space complexity: O(l1 + l2)

C++

class Solution {

public:

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {

string s1, s2;

for (const string& w1 : word1) s1 += w1;

for (const string& w2 : word2) s2 += w2;

return s1 == s2;

}

};

Solution 2: Pointers

Time complexity: O(l1 + l2)
Space complexity: O(1)

C++

class Solution {

public:

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {

int i1 = 0, j1 = 0;

int i2 = 0, j2 = 0;

while (i1 < word1.size() || i2 < word2.size()) {

char c1 = i1 < word1.size() ? word1[i1][j1++] : '\0';

char c2 = i2 < word2.size() ? word2[i2][j2++] : '\0';

if (c1 != c2) return false;

if (i1 < word1.size() && j1 == word1[i1].length())

++i1, j1 = 0;

if (i2 < word2.size() && j2 == word2[i2].length())

++i2, j2 = 0;

}

return true;

}

};

花花酱 Min Heap SP21

By zxi on November 18, 2020

C++

// Author: Huahua

#include <assert.h>

#include <iostream>

#include <vector>

using namespace std;

class MinHeap {

public:

// Return the min element.

int peek() const { return data_[0]; }

// Extract the min element.

int pop() {

// Swap the min element with the last one. O(1)

swap(data_.back(), data_[0]);

// Get the min element. O(1)

int min_el = data_.back();

// Evict the min element. O(1)

data_.pop_back();

// Maintain heap property. θ(logn)

heapifyDown(0);

return min_el;

}

// Add a new element to the heap.

void push(int key) {

// Add the element to the end of the array. O(1)

data_.push_back(key);

// Maintain heap property. θ(logn)

heapifyUp(data_.size() - 1);

}

// Return the size of the heap.

int size() const { return data_.size(); }

private:

void heapifyUp(int index) {

// Stop at root.

if (index == 0) return;

int parent = (index - 1) / 2;

// Stop if greater or euqal to parent.

if (data_[index] >= data_[parent]) return;

// Swap with parent.

swap(data_[index], data_[parent]);

// Continue heapifyUp on parent.

heapifyUp(parent);

}

void heapifyDown(int index) {

int left = index * 2 + 1;

int right = index * 2 + 2;

// Stop if has no left child.

if (left >= data_.size()) return;

// Get the min child.

int min_child =

right < data_.size() && data_[right] < data_[left] ? right : left;

// Stop if less or euqal to min child.

if (data_[index] <= data_[min_child])

return;

// Swap with min child.

swap(data_[index], data_[min_child]);

// Continue heapifyDown on min_child.

heapifyDown(min_child);

}

vector<int> data_;

};

int main() {

vector<int> data{5,1,3,5,3,4,3,7};

MinHeap heap;

for (int x : data)

heap.push(x);

vector<int> output;

while (heap.size())

output.push_back(heap.pop());

assert(output == vector<int>({1,3,3,3,4,5,5,7}));

}

Python3

# Author: Huahua

class MinHeap:

def __init__(self, data = None):

self.data = list(data) if data else []

for i in range((len(self.data)) // 2, -1, -1):

self.heapifyDown(i)

def push(self, key):

self.data.append(key)

self.heapifyUp(len(self.data) - 1)

def pop(self):

self.swap(0, -1)

min_el = self.data.pop()

self.heapifyDown(0)

return min_el

def size(self):

return len(self.data)

def swap(self, i, j):

self.data[i], self.data[j] = self.data[j], self.data[i]

def heapifyDown(self, i):

smallest = i

for c in [2 * i + 1, 2 * i + 2]:

if c < self.size() and self.data[c] < self.data[smallest]: smallest = c

if smallest != i:

self.swap(i, smallest)

self.heapifyDown(smallest)

def heapifyUp(self, i):

if i == 0: return

parent = (i - 1) // 2

if self.data[i] >= self.data[parent]: return

self.swap(i, parent)

self.heapifyUp(parent)

def test():

data = [5,1,3,5,3,4,3,7]

heap = MinHeap()

for x in data: heap.push(x)

output = []

while heap.size():

output.append(heap.pop())

assert output == sorted(data)

def testBuildHeap():

data = [5,1,3,5,3,4,3,7]

heap = MinHeap(data)

output = []

while heap.size():

output.append(heap.pop())

assert output == sorted(data)

def main():

test()

testBuildHeap()

if __name__ == '__main__':

main()

花花酱 LeetCode 1658. Minimum Operations to Reduce X to Zero

By zxi on November 14, 2020

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it’s possible, otherwise, return -1.

Example 1:

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

Example 2:

Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:

Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴
1 <= x <= 10⁹

Solution1: Prefix Sum + Hashtable

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& nums, int x) {

const int n = nums.size();

vector<int> l(n), r(n);

unordered_map<int, int> ml, mr;

ml[0] = mr[0] = -1;

for (int i = 0; i < n; ++i) {

l[i] = nums[i] + (i > 0 ? l[i - 1] : 0);

r[i] = nums[n - i - 1] + (i > 0 ? r[i - 1]: 0);

ml[l[i]] = mr[r[i]] = i;

}

int ans = INT_MAX;

for (int i = 0; i < n; ++i) {

int s1 = x - l[i];

auto it1 = mr.find(s1);

if (it1 != mr.end()) ans = min(ans, i + 1 + it1->second + 1);

int s2 = x - r[i];

auto it2 = ml.find(s2);

if (it2 != ml.end()) ans = min(ans, i + 1 + it2->second + 1);

}

return ans > n ? -1 : ans;

}

};

Solution2: Sliding Window

Find the longest sliding window whose sum of elements equals sum(nums) – x
ans = n – window_size

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& nums, int x) {

const int n = nums.size();

int target = accumulate(begin(nums), end(nums), 0) - x;

int ans = INT_MAX;

for (int s = 0, l = 0, r = 0; r < n; ++r) {

s += nums[r];

while (s > target && l <= r) s -= nums[l++];

if (s == target) ans = min(ans, n - (r - l + 1));

}

return ans > n ? -1 : ans;

}

};

花花酱 LeetCode 1657. Determine if Two Strings Are Close

By zxi on November 14, 2020

Two strings are considered close if you can attain one from the other using the following operations:

Operation 1: Swap any two existing characters.
- For example, abcde -> aecdb
Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
- For example, aacabb -> bbcbaa (all a‘s turn into b‘s, and all b‘s turn into a‘s)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

Example 1:

Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"

Example 2:

Input: word1 = "a", word2 = "aa"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3:

Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Explanation: You can attain word2 from word1 in 3 operations.
Apply Operation 1: "cabbba" -> "caabbb"
Apply Operation 2: "caabbb" -> "baaccc"
Apply Operation 2: "baaccc" -> "abbccc"

Example 4:

Input: word1 = "cabbba", word2 = "aabbss"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any amount of operations.

Constraints:

1 <= word1.length, word2.length <= 10⁵
word1 and word2 contain only lowercase English letters.

Solution: Hashtable

Two strings are close:
1. Have the same length, ccabbb => 6 == aabccc => 6
2. Have the same char set, ccabbb => (a, b, c) == aabccc => (a, b, c)
3. Have the same sorted char counts ccabbb => (1, 2, 3) == aabccc => (1, 2, 3)

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool closeStrings(string word1, string word2) {

const int l1 = word1.length();

const int l2 = word2.length();

if (l1 != l2) return false;

vector<int> f1(128), f2(128);

vector<int> s1(128), s2(128);

for (char c: word1) ++f1[c], s1[c] = 1;

for (char c: word2) ++f2[c], s2[c] = 1;

sort(begin(f1), end(f1));

sort(begin(f2), end(f2));

return f1 == f2 && s1 == s2;

}

};

Python3

# Author: Huahua

class Solution:

def closeStrings(self, word1: str, word2: str) -> bool:

c1, c2 = Counter(word1), Counter(word2)

return all([len(word1) == len(word2),

c1.keys() == c2.keys(),

sorted(c1.values()) == sorted(c2.values())])

花花酱 LeetCode 1656. Design an Ordered Stream

By zxi on November 14, 2020

There are n (id, value) pairs, where id is an integer between 1 and n and value is a string. No two pairs have the same id.

Design a stream that takes the n pairs in an arbitrary order, and returns the values over several calls in increasing order of their ids.

Implement the OrderedStream class:

OrderedStream(int n) Constructs the stream to take n values and sets a current ptr to 1.
String[] insert(int id, String value) Stores the new (id, value) pair in the stream. After storing the pair:
- If the stream has stored a pair with id = ptr, then find the longest contiguous incrementing sequence of ids starting with id = ptr and return a list of the values associated with those ids in order. Then, update ptr to the last id + 1.
- Otherwise, return an empty list.

Example:

Input
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
Output
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]
Explanation
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns [].
os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"].
os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"].
os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns [].
os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].

Solution: Straight Forward

Time complexity: O(n) in total
Space complexity: O(n)

C++

// Author: Huahua

class OrderedStream {

public:

OrderedStream(int n): data_(n + 1) {}

vector<string> insert(int id, string value) {

data_[id] = value;

vector<string> ans;

if (ptr_ == id)

while (ptr_ < data_.size() && !data_[ptr_].empty())

ans.push_back(data_[ptr_++]);

return ans;

}

private:

int ptr_ = 1;

vector<string> data_;

};

Python3

# Author: Huahua

class OrderedStream:

def __init__(self, n: int):

self.data = [None] * (n + 1)

self.ptr = 1

def insert(self, id: int, value: str) -> List[str]:

self.data[id] = value

if id == self.ptr:

while self.ptr < len(self.data) and self.data[self.ptr]:

self.ptr += 1

return self.data[id:self.ptr]

return []

Huahua's Tech Road

花花酱 LeetCode 1662. Check If Two String Arrays are Equivalent

Solution1: Construct the string

C++

Solution 2: Pointers

C++

花花酱 Min Heap SP21

C++

Python3

花花酱 LeetCode 1658. Minimum Operations to Reduce X to Zero

Solution1: Prefix Sum + Hashtable

C++

Solution2: Sliding Window

C++

花花酱 LeetCode 1657. Determine if Two Strings Are Close

Solution: Hashtable

C++

Python3

花花酱 LeetCode 1656. Design an Ordered Stream

Solution: Straight Forward

C++

Python3