Posts published in “Hashtable”

花花酱 LeetCode 205. Isomorphic Strings

By zxi on December 5, 2021

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Constraints:

1 <= s.length <= 5 * 10⁴
t.length == s.length
s and t consist of any valid ascii character.

Solution: Counting

The # of distinct pairs e.g. (s[i], t[i]), should be equal to the # of distinct chars in s and t.
ex1:
set of pairs: {(e, a), (g,d)}
set of s: {e, g}
set of t: {a, d}
For s, we can replace e with a, and replace g with d.
ex2:
set of pairs: {(f, b), (o, a), (o, r)}
set of s: {f, o}
set of t: {b, a, r}
o can not pair with a, r at the same time.
ex3:
set of pairs: {(p, t), (a, i), (e, l), (r, e)}
set of s: {p, a, e, r}
set of t: {t, i, l, e}

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

C++

// Author: Huahua

class Solution {

public:

bool isIsomorphic(string s, string t) {

const int n = s.length();

unordered_set<int> s1;

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

s1.insert((s[i] << 8) | t[i]);

unordered_set<int> s2(begin(s), end(s));

unordered_set<int> s3(begin(t), end(t));

return s1.size() == s2.size() && s2.size() == s3.size();

}

};

花花酱 LeetCode 2094. Finding 3-Digit Even Numbers

By zxi on December 4, 2021

You are given an integer array digits, where each element is a digit. The array may contain duplicates.

You need to find all the unique integers that follow the given requirements:

The integer consists of the concatenation of three elements from digits in any arbitrary order.
The integer does not have leading zeros.
The integer is even.

For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.

Return a sorted array of the unique integers.

Example 1:

Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: 
All the possible integers that follow the requirements are in the output array. 
Notice that there are no odd integers or integers with leading zeros.

Example 2:

Input: digits = [2,2,8,8,2]
Output: [222,228,282,288,822,828,882]
Explanation: 
The same digit can be used as many times as it appears in digits. 
In this example, the digit 8 is used twice each time in 288, 828, and 882.

Example 3:

Input: digits = [3,7,5]
Output: []
Explanation: 
No even integers can be formed using the given digits.

Example 4:

Input: digits = [0,2,0,0]
Output: [200]
Explanation: 
The only valid integer that can be formed with three digits and no leading zeros is 200.

Example 5:

Input: digits = [0,0,0]
Output: []
Explanation: 
All the integers that can be formed have leading zeros. Thus, there are no valid integers.

Constraints:

3 <= digits.length <= 100
0 <= digits[i] <= 9

Solution: Enumerate all three digits even numbers

Check 100, 102, … 998. Use a hashtable to check whether all digits are covered by the given digits.

Time complexity: O(1000*lg(1000))
Space complexity: O(10)

C++

// Author: Huahua

class Solution {

public:

vector<int> findEvenNumbers(vector<int>& digits) {

vector<int> counts(10);

for (int d : digits) ++counts[d];

vector<int> ans;

for (int x = 100; x < 1000; x += 2) {

bool valid = true;

vector<int> c(10);

for (int t = x; t > 0; t /= 10)

valid &= (++c[t % 10] <= counts[t % 10]);

if (valid) ans.push_back(x);

}

return ans;

}

};

花花酱 LeetCode 187. Repeated DNA Sequences

By zxi on November 28, 2021

The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.

For example, "ACGAATTCCG" is a DNA sequence.

When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

Example 1:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

Example 2:

Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]

Constraints:

1 <= s.length <= 10⁵
s[i] is either 'A', 'C', 'G', or 'T'.

Solution: Hashtable

Store each subsequence into the hashtable, add it into the answer array when it appears for the second time.

Time complexity: O(n*l)
Space complexity: O(n*l) -> O(n) / string_view

C++

// Author: Huahua

class Solution {

public:

vector<string> findRepeatedDnaSequences(string_view s) {

constexpr int kLen = 10;

const int n = s.length();

unordered_map<string_view, int> m;

vector<string> ans;

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

if (++m[s.substr(i, kLen)] == 2)

ans.emplace_back(s.substr(i, kLen));

return ans;

}

};

Optimization

There are 4 type of letters, each can be encoded into 2 bits. We can represent the 10-letter-long string using 20 lowest bit of a int32. We can use int as key for the hashtable.

A -> 00
C -> 01
G -> 10
T -> 11

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

C++

// Author: Huahua

class Solution {

public:

vector<string> findRepeatedDnaSequences(string s) {

constexpr int kLen = 10;

constexpr int mask = (1 << (2 * kLen)) -1;

const int n = s.length();

unordered_map<int, int> m;

array<int, 128> km;

km['A'] = 0;

km['C'] = 1;

km['G'] = 2;

km['T'] = 3;

vector<string> ans;

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

key = ((key << 2) & mask) | km[s[i]];

if (i < kLen - 1) continue;

if (++m[key] == 2)

ans.push_back(s.substr(i - kLen + 1, kLen));

}

return ans;

}

};

花花酱 LeetCode 166. Fraction to Recurring Decimal

By zxi on November 28, 2021

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 10⁴ for all the given inputs.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 2, denominator = 3
Output: "0.(6)"

Example 4:

Input: numerator = 4, denominator = 333
Output: "0.(012)"

Example 5:

Input: numerator = 1, denominator = 5
Output: "0.2"

Constraints:

-2³¹ <= numerator, denominator <= 2³¹ - 1
denominator != 0

Solution: Hashtable

Time complexity: O(?)

C++

// Author: Huahua

class Solution {

public:

string fractionToDecimal(int numerator, int denominator) {

stringstream ss,ss2;

long long n = numerator;

long long d = denominator;

if ( n > 0 && d < 0 || n < 0 && d > 0) {

ss << "-";

n = abs(n);

d = abs(d);

}

ss << (n / d);

long long r = n % d;

bool loop = false;

int count = 0;

int loop_start;

if (r) {

n = r;

ss << ".";

unordered_map<int, int> rs;

rs[r] = 0;

while (r) {

n = n*10;

r = n % d;

ss2 << (n / d);

n = r;

if (r && rs.count(r)) {

loop = true;

loop_start = rs[r];

break;

}

rs[r] = ++count;

}

if (loop) {

auto s2 = ss2.str();

ss << s2.substr(0, loop_start) << "(" << s2.substr(loop_start) << ")";

} else {

ss << ss2.str();

}

return ss.str();

}

};

花花酱 LeetCode 2085. Count Common Words With One Occurrence

By zxi on November 27, 2021

Given two string arrays words1 and words2, return the number of strings that appear exactly once in each of the two arrays.

Example 1:

Input: words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is"]
Output: 2
Explanation:
- "leetcode" appears exactly once in each of the two arrays. We count this string.
- "amazing" appears exactly once in each of the two arrays. We count this string.
- "is" appears in each of the two arrays, but there are 2 occurrences of it in words1. We do not count this string.
- "as" appears once in words1, but does not appear in words2. We do not count this string.
Thus, there are 2 strings that appear exactly once in each of the two arrays.

Example 2:

Input: words1 = ["b","bb","bbb"], words2 = ["a","aa","aaa"]
Output: 0
Explanation: There are no strings that appear in each of the two arrays.

Example 3:

Input: words1 = ["a","ab"], words2 = ["a","a","a","ab"]
Output: 1
Explanation: The only string that appears exactly once in each of the two arrays is "ab".

Constraints:

1 <= words1.length, words2.length <= 1000
1 <= words1[i].length, words2[j].length <= 30
words1[i] and words2[j] consists only of lowercase English letters.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int countWords(vector<string>& words1, vector<string>& words2) {

unordered_map<string, int> c1;

unordered_map<string, int> c2;

for (const string& w : words1) ++c1[w];

for (const string& w : words2) ++c2[w];

int ans = 0;

for (const auto& [w, c] : c1)

if (c == 1 && c2[w] == 1) ++ans;

return ans;

}

};