Posts tagged as “data structure”

花花酱 LeetCode 2227. Encrypt and Decrypt Strings

By zxi on April 3, 2022

You are given a character array keys containing unique characters and a string array values containing strings of length 2. You are also given another string array dictionary that contains all permitted original strings after decryption. You should implement a data structure that can encrypt or decrypt a 0-indexed string.

A string is encrypted with the following process:

For each character c in the string, we find the index i satisfying keys[i] == c in keys.
Replace c with values[i] in the string.

A string is decrypted with the following process:

For each substring s of length 2 occurring at an even index in the string, we find an i such that values[i] == s. If there are multiple valid i, we choose any one of them. This means a string could have multiple possible strings it can decrypt to.
Replace s with keys[i] in the string.

Implement the Encrypter class:

Encrypter(char[] keys, String[] values, String[] dictionary) Initializes the Encrypter class with keys, values, and dictionary.
String encrypt(String word1) Encrypts word1 with the encryption process described above and returns the encrypted string.
int decrypt(String word2) Returns the number of possible strings word2 could decrypt to that also appear in dictionary.

Example 1:

Input
["Encrypter", "encrypt", "decrypt"]
[[['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]], ["abcd"], ["eizfeiam"]]
Output

[null, “eizfeiam”, 2]

Explanation Encrypter encrypter = new Encrypter([[‘a’, ‘b’, ‘c’, ‘d’], [“ei”, “zf”, “ei”, “am”], [“abcd”, “acbd”, “adbc”, “badc”, “dacb”, “cadb”, “cbda”, “abad”]); encrypter.encrypt(“abcd”); // return “eizfeiam”. // ‘a’ maps to “ei”, ‘b’ maps to “zf”, ‘c’ maps to “ei”, and ‘d’ maps to “am”. encrypter.decrypt(“eizfeiam”); // return 2. // “ei” can map to ‘a’ or ‘c’, “zf” maps to ‘b’, and “am” maps to ‘d’. // Thus, the possible strings after decryption are “abad”, “cbad”, “abcd”, and “cbcd”. // 2 of those strings, “abad” and “abcd”, appear in dictionary, so the answer is 2.

Constraints:

1 <= keys.length == values.length <= 26
values[i].length == 2
1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
All keys[i] and dictionary[i] are unique.
1 <= word1.length <= 2000
1 <= word2.length <= 200
All word1[i] appear in keys.
word2.length is even.
keys, values[i], dictionary[i], word1, and word2 only contain lowercase English letters.
At most 200 calls will be made to encrypt and decrypt in total.

Solution:

For encryption, follow the instruction. Time complexity: O(len(word)) = O(2000)
For decryption, try all words in the dictionary and encrypt them and compare the encrypted string with the word to decrypt. Time complexity: O(sum(len(word_in_dict))) = O(100*100)

Worst case: 200 calls to decryption, T = 200 * O(100 * 100) = O(2*10⁶)

C++

// Author: Huahua

class Encrypter {

public:

Encrypter(vector<char>& keys,

vector<string>& values,

vector<string>& dictionary):

vals(26),

dict(dictionary) {

for (size_t i = 0; i < keys.size(); ++i)

vals[keys[i] - 'a'] = values[i];

}

string encrypt(string word1) {

string ans;

for (char c : word1)

ans += vals[c - 'a'];

return ans;

}

int decrypt(string word2) {

return count_if(begin(dict), end(dict), [&](const string& w){

return encrypt(w) == word2;

});

}

private:

vector<string> vals;

vector<string> dict;

};

Optimization

Pre-compute answer for all the words in dictionary.

decrypt: Time complexity: O(1)

C++

// Author: Huahua

class Encrypter {

public:

Encrypter(vector<char>& keys,

vector<string>& values,

vector<string>& dictionary):

vals(26) {

for (size_t i = 0; i < keys.size(); ++i)

vals[keys[i] - 'a'] = values[i];

for (const string& w : dictionary)

++counts[encrypt(w)];

}

string encrypt(string word1) {

string ans;

for (char c : word1)

ans += vals[c - 'a'];

return ans;

}

int decrypt(string word2) {

auto it = counts.find(word2);

return it == counts.end() ? 0 : it->second;

}

private:

vector<string> vals;

unordered_map<string, int> counts;

};

花花酱 LeetCode 2102. Sequentially Ordinal Rank Tracker

By zxi on December 12, 2021

A scenic location is represented by its name and attractiveness score, where name is a unique string among all locations and score is an integer. Locations can be ranked from the best to the worst. The higher the score, the better the location. If the scores of two locations are equal, then the location with the lexicographically smaller name is better.

You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:

Adding scenic locations, one at a time.
Querying the i^th best location of all locations already added, where i is the number of times the system has been queried (including the current query).
- For example, when the system is queried for the 4^th time, it returns the 4^th best location of all locations already added.

Note that the test data are generated so that at any time, the number of queries does not exceed the number of locations added to the system.

Implement the SORTracker class:

SORTracker() Initializes the tracker system.
void add(string name, int score) Adds a scenic location with name and score to the system.
string get() Queries and returns the i^th best location, where i is the number of times this method has been invoked (including this invocation).

Example 1:

Input

["SORTracker", "add", "add", "get", "add", "get", "add", "get", "add", "get", "add", "get", "get"]

[[], ["bradford", 2], ["branford", 3], [], ["alps", 2], [], ["orland", 2], [], ["orlando", 3], [], ["alpine", 2], [], []]

Output

[null, null, null, "branford", null, "alps", null, "bradford", null, "bradford", null, "bradford", "orland"]

Explanation

SORTracker tracker = new SORTracker(); // Initialize the tracker system.

tracker.add("bradford", 2); // Add location with name="bradford" and score=2 to the system.

tracker.add("branford", 3); // Add location with name="branford" and score=3 to the system.

tracker.get(); // The sorted locations, from best to worst, are: branford, bradford.

// Note that branford precedes bradford due to its higher score (3 > 2).

// This is the 1st time get() is called, so return the best location: "branford".

tracker.add("alps", 2); // Add location with name="alps" and score=2 to the system.

tracker.get(); // Sorted locations: branford, alps, bradford.

// Note that alps precedes bradford even though they have the same score (2).

// This is because "alps" is lexicographically smaller than "bradford".

// Return the 2nd best location "alps", as it is the 2nd time get() is called.

tracker.add("orland", 2); // Add location with name="orland" and score=2 to the system.

tracker.get(); // Sorted locations: branford, alps, bradford, orland.

// Return "bradford", as it is the 3rd time get() is called.

tracker.add("orlando", 3); // Add location with name="orlando" and score=3 to the system.

tracker.get(); // Sorted locations: branford, orlando, alps, bradford, orland.

// Return "bradford".

tracker.add("alpine", 2); // Add location with name="alpine" and score=2 to the system.

tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland.

// Return "bradford".

tracker.get(); // Sorted locations: branford, orlando, alpine, alps, bradford, orland.

// Return "orland".

Constraints:

name consists of lowercase English letters, and is unique among all locations.
1 <= name.length <= 10
1 <= score <= 10⁵
At any time, the number of calls to get does not exceed the number of calls to add.
At most 4 * 10⁴ calls in total will be made to add and get.

Solution: TreeSet w/ Iterator

Use a treeset to store all the entries and use a iterator that points to the entry to return. When inserting a new entry into the tree, if it’s higher than the current element then let the iterator go backward one step.

Time complexity: add O(logn) / get O(1)

C++

// Author: Huahua

class SORTracker {

public:

SORTracker() {}

void add(string name, int score) {

if (*s.emplace(-score, name).first < *cit) --cit;

}

string get() {

return (cit++)->second;

}

private:

set<pair<int, string>> s;

// Note: cit points to begin(s) after first insertion.

set<pair<int, string>>::const_iterator cit = end(s);

};

花花酱 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 155. Min Stack

By zxi on November 28, 2021

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output

[null,null,null,null,-3,null,0,-2]

Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Constraints:

-2³¹ <= val <= 2³¹ - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 10⁴ calls will be made to push, pop, top, and getMin.

Solution 1: Two Stacks

One normal stack, one monotonic stack to store the min values.

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

C++

// Author: Huahua

class MinStack {

public:

void push(int x) {

m_data.push(x);

if (m_s.empty() || x <= m_s.top())

m_s.push(x);

}

void pop() {

if (!m_s.empty() && m_data.top() == m_s.top())

m_s.pop();

m_data.pop();

}

int top() {

return m_data.top();

}

int getMin() {

return m_s.empty() ? m_data.top() : m_s.top();

}

private:

stack<int> m_data;

stack<int> m_s;

};

花花酱 LeetCode 1865. Finding Pairs With a Certain Sum

By zxi on August 4, 2021

You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:

Add a positive integer to an element of a given index in the array nums2.
Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value (0 <= i < nums1.length and 0 <= j < nums2.length).

Implement the FindSumPairs class:

FindSumPairs(int[] nums1, int[] nums2) Initializes the FindSumPairs object with two integer arrays nums1 and nums2.
void add(int index, int val) Adds val to nums2[index], i.e., apply nums2[index] += val.
int count(int tot) Returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.

Example 1:

Input
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
Output
[null, 8, null, 2, 1, null, null, 11]
Explanation
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7); // return 8; pairs (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) make 2 + 5 and pairs (5,1), (5,5) make 3 + 4
findSumPairs.add(3, 2); // now nums2 = [1,4,5,4,5,4] 
findSumPairs.count(8); // return 2; pairs (5,2), (5,4) make 3 + 5 
findSumPairs.count(4); // return 1; pair (5,0) makes 3 + 1 
findSumPairs.add(0, 1); // now nums2 = [2,4,5,4,5,4] 
findSumPairs.add(1, 1); // now nums2 = [2,5,5,4,5,4] 
findSumPairs.count(7); // return 11; pairs (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) make 2 + 5 and pairs (5,3), (5,5) make 3 + 4

Constraints:

1 <= nums1.length <= 1000
1 <= nums2.length <= 10⁵
1 <= nums1[i] <= 10⁹
1 <= nums2[i] <= 10⁵
0 <= index < nums2.length
1 <= val <= 10⁵
1 <= tot <= 10⁹
At most 1000 calls are made to add and count each.

Solution: HashTable

Note nums1 and nums2 are unbalanced. Brute force method will take O(m*n) = O(10³*10⁵) = O(10⁸) for each count call which will TLE. We could use a hashtable to store the counts of elements from nums2, and only iterate over nums1 to reduce the time complexity.

Time complexity:

init: O(m) + O(n)
add: O(1)
count: O(m)

Total time is less than O(10⁶)

Space complexity: O(m + n)

C++

// Author: Huahua

class FindSumPairs {

public:

FindSumPairs(vector<int>& nums1,

vector<int>& nums2): nums1_(nums1), nums2_(nums2) {

for (int x : nums2_) ++freq_[x];

}

void add(int index, int val) {

if (--freq_[nums2_[index]] == 0)

freq_.erase(nums2_[index]);

++freq_[nums2_[index] += val];

}

int count(int tot) {

int ans = 0;

for (int a : nums1_) {

auto it = freq_.find(tot - a);

if (it != freq_.end()) ans += it->second;

}

return ans;

}

private:

vector<int> nums1_;

vector<int> nums2_;

unordered_map<int, int> freq_;

};

Python3

# Author: Huahua

class FindSumPairs:

def __init__(self, nums1: List[int], nums2: List[int]):

self.nums1 = nums1

self.nums2 = nums2

self.freq = Counter(nums2)

def add(self, index: int, val: int) -> None:

self.freq.subtract((self.nums2[index],))

self.nums2[index] += val

self.freq.update((self.nums2[index],))

def count(self, tot: int) -> int:

return sum(self.freq[tot - a] for a in self.nums1)