Huahua’s Tech Road

花花酱 LeetCode 1813. Sentence Similarity III

By zxi on April 3, 2021

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. For example, "Hello World", "HELLO", "hello world hello world" are all sentences. Words consist of only uppercase and lowercase English letters.

Two sentences sentence1 and sentence2 are similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal. For example, sentence1 = "Hello my name is Jane" and sentence2 = "Hello Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in sentence2.

Given two sentences sentence1 and sentence2, return true if sentence1 and sentence2 are similar. Otherwise, return false.

Example 1:

Input: sentence1 = "My name is Haley", sentence2 = "My Haley"
Output: true
Explanation: sentence2 can be turned to sentence1 by inserting "name is" between "My" and "Haley".

Example 2:

Input: sentence1 = "of", sentence2 = "A lot of words"
Output: false
Explanation: No single sentence can be inserted inside one of the sentences to make it equal to the other.

Example 3:

Input: sentence1 = "Eating right now", sentence2 = "Eating"
Output: true
Explanation: sentence2 can be turned to sentence1 by inserting "right now" at the end of the sentence.

Example 4:

Input: sentence1 = "Luky", sentence2 = "Lucccky"
Output: false

Constraints:

1 <= sentence1.length, sentence2.length <= 100
sentence1 and sentence2 consist of lowercase and uppercase English letters and spaces.
The words in sentence1 and sentence2 are separated by a single space.

Solution: Dequeue / Common Prefix + Suffix

Break sequences to words, store them in two deques. Pop the common prefix and suffix. At least one of the deque should be empty.

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

C++

// Author: Huahua

class Solution {

public:

bool areSentencesSimilar(string s1, string s2) {

auto getWords = [](const string& s) {

stringstream ss(s);

deque<string> words;

while (ss) {

words.emplace_back("");

ss >> words.back();

}

return words;

};

deque<string> w1 = getWords(s1), w2 = getWords(s2);

while (w1.size() && w2.size() && w1.front() == w2.front())

w1.pop_front(), w2.pop_front();

while (w1.size() && w2.size() && w1.back() == w2.back())

w1.pop_back(), w2.pop_back();

return w1.empty() || w2.empty();

}

};

Python3

# Author: Huahua

class Solution:

def areSentencesSimilar(self, s1: str, s2: str) -> bool:

w1 = deque(s1.split())

w2 = deque(s2.split())

while w1 and w2 and w1[0] == w2[0]:

w1.popleft(), w2.popleft()

while w1 and w2 and w1[-1] == w2[-1]:

w1.pop(), w2.pop()

return len(w1) * len(w2) == 0

花花酱 LeetCode 1812. Determine Color of a Chessboard Square

By zxi on April 3, 2021

You are given coordinates, a string that represents the coordinates of a square of the chessboard. Below is a chessboard for your reference.

Return true if the square is white, and false if the square is black.

The coordinate will always represent a valid chessboard square. The coordinate will always have the letter first, and the number second.

Example 1:

Input: coordinates = "a1"
Output: false
Explanation: From the chessboard above, the square with coordinates "a1" is black, so return false.

Example 2:

Input: coordinates = "h3"
Output: true
Explanation: From the chessboard above, the square with coordinates "h3" is white, so return true.

Example 3:

Input: coordinates = "c7"
Output: false

Constraints:

coordinates.length == 2
'a' <= coordinates[0] <= 'h'
'1' <= coordinates[1] <= '8'

Solution: Mod2

return (row_index + col_index) % 2 == 0

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

C++

class Solution {

public:

bool squareIsWhite(string coordinates) {

return ((coordinates[0] - 'a') + (coordinates[1] - '0')) % 2 == 0;

}

};

花花酱 LeetCode 1808. Maximize Number of Nice Divisors

By zxi on March 27, 2021

You are given a positive integer primeFactors. You are asked to construct a positive integer n that satisfies the following conditions:

The number of prime factors of n (not necessarily distinct) is at most primeFactors.
The number of nice divisors of n is maximized. Note that a divisor of n is nice if it is divisible by every prime factor of n. For example, if n = 12, then its prime factors are [2,2,3], then 6 and 12 are nice divisors, while 3 and 4 are not.

Return the number of nice divisors of n. Since that number can be too large, return it modulo 10⁹ + 7.

Note that a prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. The prime factors of a number n is a list of prime numbers such that their product equals n.

Example 1:

Input: primeFactors = 5
Output: 6
Explanation: 200 is a valid value of n.
It has 5 prime factors: [2,2,2,5,5], and it has 6 nice divisors: [10,20,40,50,100,200].
There is not other value of n that has at most 5 prime factors and more nice divisors.

Example 2:

Input: primeFactors = 8
Output: 18

Constraints:

1 <= primeFactors <= 10⁹

Solution: Math

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

C++

// Author: Huahua

class Solution {

public:

int maxNiceDivisors(int n) {

constexpr int kMod = 1e9 + 7;

auto powm = [](long base, int exp) {

long ans = 1;

while (exp) {

if (exp & 1) ans = (ans * base) % kMod;

base = (base * base) % kMod;

exp >>= 1;

}

return ans;

};

if (n <= 3) return n;

switch (n % 3) {

case 0: return powm(3, n / 3);

case 1: return (powm(3, n / 3 - 1) * 4) % kMod;

case 2: return (powm(3, n / 3) * 2) % kMod;

}

return -1;

}

};

花花酱 LeetCode 1807. Evaluate the Bracket Pairs of a String

By zxi on March 27, 2021

You are given a string s that contains some bracket pairs, with each pair containing a non-empty key.

For example, in the string "(name)is(age)yearsold", there are two bracket pairs that contain the keys "name" and "age".

You know the values of a wide range of keys. This is represented by a 2D string array knowledge where each knowledge[i] = [key_i, value_i] indicates that key key_i has a value of value_i.

You are tasked to evaluate all of the bracket pairs. When you evaluate a bracket pair that contains some key key_i, you will:

Replace key_i and the bracket pair with the key’s corresponding value_i.
If you do not know the value of the key, you will replace key_i and the bracket pair with a question mark "?" (without the quotation marks).

Each key will appear at most once in your knowledge. There will not be any nested brackets in s.

Return the resulting string after evaluating all of the bracket pairs.

Example 1:

Input: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
Output: "bobistwoyearsold"
Explanation:
The key "name" has a value of "bob", so replace "(name)" with "bob".
The key "age" has a value of "two", so replace "(age)" with "two".

Example 2:

Input: s = "hi(name)", knowledge = [["a","b"]]
Output: "hi?"
Explanation: As you do not know the value of the key "name", replace "(name)" with "?".

Example 3:

Input: s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]
Output: "yesyesyesaaa"
Explanation: The same key can appear multiple times.
The key "a" has a value of "yes", so replace all occurrences of "(a)" with "yes".
Notice that the "a"s not in a bracket pair are not evaluated.

Example 4:

Input: s = "(a)(b)", knowledge = [["a","b"],["b","a"]]
Output: "ba"

Constraints:

1 <= s.length <= 10⁵
0 <= knowledge.length <= 10⁵
knowledge[i].length == 2
1 <= key_i.length, value_i.length <= 10
s consists of lowercase English letters and round brackets '(' and ')'.
Every open bracket '(' in s will have a corresponding close bracket ')'.
The key in each bracket pair of s will be non-empty.
There will not be any nested bracket pairs in s.
key_i and value_i consist of lowercase English letters.
Each key_i in knowledge is unique.

Solution: Hashtable + Simulation

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

C++

// Author: Huahua

class Solution {

public:

string evaluate(string s, vector<vector<string>>& knowledge) {

unordered_map<string, string> m;

for (const auto& p : knowledge)

m[p[0]] = p[1];

string ans;

string cur;

bool in = false;

for (char c : s) {

if (c == '(') {

in = true;

} else if (c == ')') {

if (m.count(cur))

ans += m[cur];

else

ans += "?";

cur.clear();

in = false;

} else {

if (!in) ans += c;

else cur += c;

}

return ans;

}

};

花花酱 LeetCode 1806. Minimum Number of Operations to Reinitialize a Permutation

By zxi on March 27, 2021

You are given an even integer n. You initially have a permutation perm of size n where perm[i] == i (0-indexed).

In one operation, you will create a new array arr, and for each i:

If i % 2 == 0, then arr[i] = perm[i / 2].
If i % 2 == 1, then arr[i] = perm[n / 2 + (i - 1) / 2].

You will then assign arr to perm.

Return the minimum non-zero number of operations you need to perform on perm to return the permutation to its initial value.

Example 1:

Input: n = 2
Output: 1
Explanation: prem = [0,1] initially.
After the 1^st operation, prem = [0,1]
So it takes only 1 operation.

Example 2:

Input: n = 4
Output: 2
Explanation: prem = [0,1,2,3] initially.
After the 1^st operation, prem = [0,2,1,3]
After the 2^nd operation, prem = [0,1,2,3]
So it takes only 2 operations.

Example 3:

Input: n = 6
Output: 4

Constraints:

2 <= n <= 1000
n is even.

Solution: Brute Force / Simulation

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

C++

// Author: Huahua

class Solution {

public:

int reinitializePermutation(int n) {

vector<int> perm(n);

vector<int> arr(n);

for (int i = 0; i < n; ++i) perm[i] = i;

int ans = 0;

bool flag = true;

while (flag && ++ans) {

flag = false;

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

arr[i] = i & 1 ? perm[n / 2 + (i - 1) / 2] : perm[i / 2];

flag |= arr[i] != i;

}

swap(perm, arr);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1813. Sentence Similarity III

Solution: Dequeue / Common Prefix + Suffix

C++

Python3

花花酱 LeetCode 1812. Determine Color of a Chessboard Square

Solution: Mod2

C++

花花酱 LeetCode 1808. Maximize Number of Nice Divisors

Solution: Math

C++

花花酱 LeetCode 1807. Evaluate the Bracket Pairs of a String

Solution: Hashtable + Simulation

C++

花花酱 LeetCode 1806. Minimum Number of Operations to Reinitialize a Permutation

Solution: Brute Force / Simulation

C++