Huahua’s Tech Road

花花酱 LeetCode 211. Design Add and Search Words Data Structure

By zxi on December 5, 2021

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation 
WordDictionary wordDictionary = new WordDictionary(); 
wordDictionary.addWord("bad"); 
wordDictionary.addWord("dad"); 
wordDictionary.addWord("mad"); 
wordDictionary.search("pad"); // return False 
wordDictionary.search("bad"); // return True 
wordDictionary.search(".ad"); // return True 
wordDictionary.search("b.."); // return True

Constraints:

1 <= word.length <= 500
word in addWord consists lower-case English letters.
word in search consist of '.' or lower-case English letters.
At most 50000 calls will be made to addWord and search.

Solution: Hashtables

The first hashtable stores all the words, if there is no dot in the search pattern. Do a full match.

There are also per length hashtable to store words of length k. And do a brute force match.

Time complexity: Init: O(n*l)
search: best: O(l) worst: O(n*l)

C++

// Author: Huahua

class WordDictionary {

public:

// Adds a word into the data structure.

void addWord(string word) {

words.insert(word);

ws[word.length()].insert(word);

}

// Returns if the word is in the data structure. A word could

// contain the dot character '.' to represent any one letter.

bool search(string word) {

if (word.find(".") == string::npos)

return words.count(word);

for (const string& w : ws[word.length()])

if (match(word, w)) return true;

return false;

}

bool match(const string& p, const string& w) {

for (int i = 0; i < p.length(); ++i) {

if (p[i] == '.') continue;

if (p[i] != w[i]) return false;

}

return true;

}

private:

unordered_set<string> words;

unordered_map<int, unordered_set<string>> ws;

};

花花酱 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 202. Happy Number

By zxi on December 5, 2021

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2³¹ - 1

Solution: Simulation

We can use a hasthable to store all the number we generated so far.

Time complexity: O(L)
Space complexity: O(L)

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

unordered_set<int> s;

while (n != 1) {

if (!s.insert(n).second) return false;

n = getNext(n);

}

return true;

}

};

Optimization: Space reduction

Since the number sequence always has a cycle, we can use slow / fast pointers to detect the cycle without using a hastable.

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

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

int slow = n;

int fast = getNext(n);

do {

slow = getNext(slow);

fast = getNext(getNext(fast));

} while (slow != fast);

return slow == 1;

}

};

花花酱 LeetCode 201. Bitwise AND of Numbers Range

By zxi on December 5, 2021

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

Constraints:

0 <= left <= right <= 2³¹ - 1

Solution: Bit operation

Bitwise AND all the numbers between left and right will clear out all the low bits. Basically this question is asking to find the common prefix of left and right in the binary format.

5 = 0b0101
7 = 0b0111
the common prefix is 0b0100 which is 4.

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

C++

// Author: Huahua

class Solution {

public:

int rangeBitwiseAnd(int left, int right) {

while (right > left)

right &= (right - 1); // clears the lowest set bit.

return right;

}

};

花花酱 LeetCode 2097. Valid Arrangement of Pairs

By zxi on December 5, 2021

You are given a 0-indexed 2D integer array pairs where pairs[i] = [start_i, end_i]. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have end_i-1 == start_i.

Return any valid arrangement of pairs.

Note: The inputs will be generated such that there exists a valid arrangement of pairs.

Example 1:

Input: pairs = [[5,1],[4,5],[11,9],[9,4]]
Output: [[11,9],[9,4],[4,5],[5,1]]
Explanation:
This is a valid arrangement since end_i-1 always equals start_i.
end₀ = 9 == 9 = start₁ 
end₁ = 4 == 4 = start₂
end₂ = 5 == 5 = start₃

Example 2:

Input: pairs = [[1,3],[3,2],[2,1]]
Output: [[1,3],[3,2],[2,1]]
Explanation:
This is a valid arrangement since end_i-1 always equals start_i.
end₀ = 3 == 3 = start₁
end₁ = 2 == 2 = start₂
The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.

Example 3:

Input: pairs = [[1,2],[1,3],[2,1]]
Output: [[1,2],[2,1],[1,3]]
Explanation:
This is a valid arrangement since end_i-1 always equals start_i.
end₀ = 2 == 2 = start₁
end₁ = 1 == 1 = start₂

Constraints:

1 <= pairs.length <= 10⁵
pairs[i].length == 2
0 <= start_i, end_i <= 10⁹
start_i != end_i
No two pairs are exactly the same.
There exists a valid arrangement of pairs.

Solution: Eulerian trail

The goal of the problem is to find a Eulerian trail in the graph.

If there is a vertex whose out degree – in degree == 1 which means it’s the starting vertex. Otherwise wise, the graph must have a Eulerian circuit thus we can start from any vertex.

We can use Hierholzer’s algorithm to find it.

Time complexity: O(|V| + |E|)
Space complexity: O(|V| + |E|)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {

unordered_map<int, queue<int>> g;

unordered_map<int, int> degree; // out - in

for (const auto& p : pairs) {

g[p[0]].push(p[1]);

++degree[p[0]];

--degree[p[1]];

}

int s = pairs[0][0];

for (const auto& [u, d] : degree)

if (d == 1) s = u;

vector<vector<int>> ans;

function<void(int)> dfs = [&](int u) {

while (!g[u].empty()) {

int v = g[u].front(); g[u].pop();

dfs(v);

ans.push_back({u, v});

}

};

dfs(s);

return {rbegin(ans), rend(ans)};

}

};

Python3

# Author: Huahua

class Solution:

def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:

g = defaultdict(list)

d = defaultdict(int)

for u, v in pairs:

g[u].append(v)

d[u] += 1

d[v] -= 1

s = pairs[0][0]

for u in d:

if d[u] == 1: s = u

ans = []

def dfs(u: int) -> None:

while g[u]:

v = g[u].pop()

dfs(v)

ans.append([u, v])

dfs(s)

return ans[::-1]

Huahua's Tech Road

花花酱 LeetCode 211. Design Add and Search Words Data Structure

Solution: Hashtables

C++

花花酱 LeetCode 205. Isomorphic Strings

Solution: Counting

C++

花花酱 LeetCode 202. Happy Number

Solution: Simulation

C++

Optimization: Space reduction

C++

花花酱 LeetCode 201. Bitwise AND of Numbers Range

Solution: Bit operation

C++

花花酱 LeetCode 2097. Valid Arrangement of Pairs

Solution: Eulerian trail

C++

Python3