Posts published in “Hashtable”

花花酱 LeetCode 220. Contains Duplicate III

By zxi on December 20, 2018

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Solution: Sliding Window + Multiset (OrderedSet)

Maintaining a sliding window of sorted numbers of k + 1. After the i-th number was inserted into the sliding window, check whether its left and right neighbors satisfy abs(nums[i] – neighbor) <= t

Time complexity: O(nlogk)
Space complexity: O(k)

C++

// Author: Huahua, running time: 12 ms

class Solution {

public:

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {

multiset<long> s;

for (int i = 0; i < nums.size(); ++i) {

if (i > k)

s.erase(s.find(nums[i - k - 1]));

auto it = s.insert(nums[i]);

if (it != begin(s) && *it - *prev(it) <= t)

return true;

if (next(it) != end(s) && *next(it) - *it <= t)

return true;

}

return false;

}

};

花花酱 LeetCode 954. Array of Doubled Pairs

By zxi on December 9, 2018

Problem

Given an array of integers A with even length, return true if and only if it is possible to reorder it such that A[2 * i + 1] = 2 * A[2 * i] for every 0 <= i < len(A) / 2.

Example 1:

Input: [3,1,3,6]
Output: false

Example 2:

Input: [2,1,2,6]
Output: false

Example 3:

Input: [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Example 4:

Input: [1,2,4,16,8,4]
Output: false

Note:

0 <= A.length <= 30000
A.length is even
-100000 <= A[i] <= 100000

Solution 1:

Time complexity: O(N + 100000 * 2)

Space complexity: O(100000 * 2)

C++

// Author: Huahua, 108 ms

class Solution {

public:

bool canReorderDoubled(vector<int>& A) {

const int kMaxN = 100000;

vector<int> p(kMaxN + 1);

vector<int> n(kMaxN + 1);

for (int a : A) {

if (a >= 0) ++p[a];

else ++n[-a];

}

for (int i = 0; i <= kMaxN / 2; ++i) {

if (p[i] && (p[i * 2] -= p[i]) < 0) return false;

if (n[i] && (n[i * 2] -= n[i]) < 0) return false;

}

return true;

}

};

Solution 2:

Time complexity: O(NlogN)

Space complexity: O(N)

C++

// Author: Huahua, 108 ms

class Solution {

public:

bool canReorderDoubled(vector<int>& A) {

unordered_map<int, int> c;

for (int a : A) ++c[a];

vector<int> keys;

for (const auto &kv : c) keys.push_back(kv.first);

sort(begin(keys), end(keys), [](int a, int b) { return abs(a) < abs(b); });

for (int key : keys)

if (c[key] && (c[key * 2] -= c[key]) < 0) return false;

return true;

}

};

花花酱 LeetCode 953. Verifying an Alien Dictionary

By zxi on December 9, 2018

Problem

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

Example 1:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Example 2:

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

Example 3:

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

Note:

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
All characters in words[i] and order are english lowercase letters.

Solution: Hashtable

Time complexity: O(sum(len(words[i])))

Space complexity: O(26)

C++

// Author: Huahua, 8 ms

class Solution {

public:

bool isAlienSorted(vector<string>& words, string order) {

vector<char> m(26);

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

m[order[i] - 'a'] = 'a' + i;

for (int i = 0; i < words.size(); ++i) {

for (int j = 0; j < words[i].length(); ++j)

words[i][j] = m[words[i][j] - 'a'];

if (i > 0 && words[i] < words[i - 1]) return false;

}

return true;

}

};

花花酱 LeetCode 648. Replace Words

By zxi on November 8, 2018

Problem

https://leetcode.com/problems/replace-words/description/

In English, we have a concept called root, which can be followed by some other words to form another longer word – let’s call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Note:

The input will only have lower-case letters.
1 <= dict words number <= 1000
1 <= sentence words number <= 1000
1 <= root length <= 100
1 <= sentence words length <= 1000

Solution 1: HashTable

Time complexity: O(sum(w^2))

Space complexity: O(sum(l))

// Author: Huahua, Running time: 84 ms

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

unordered_set<string> d(begin(dict), end(dict));

sentence.push_back(' ');

string output;

string word;

bool found = false;

for (char c : sentence) {

if (c == ' ') {

if (!output.empty()) output += ' ';

output += word;

word = "";

found = false;

continue;

}

if (found) continue;

word += c;

if (d.count(word)) {

found = true;

}

return output;

}

};

Solution2: Trie

Time complexity: O(sum(l) + n)

Space complexity: O(sum(l) * 26)

// Author: Huahua, running time: 48 ms

class TrieNode {

public:

TrieNode(): children(26), is_word(false) {}

~TrieNode() {

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

if (children[i]) {

delete children[i];

children[i] = nullptr;

}

vector<TrieNode*> children;

bool is_word;

};

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

TrieNode root;

for (const string& word : dict) {

TrieNode* cur = &root;

for (char c : word) {

if (!cur->children[c - 'a']) cur->children[c - 'a'] = new TrieNode();

cur = cur->children[c - 'a'];

}

cur->is_word = true;

}

string ans;

stringstream ss(sentence);

string word;

while (ss >> word) {

TrieNode* cur = &root;

bool found = false;

int len = 0;

for (char c : word) {

cur = cur->children[c - 'a'];

if (!cur) break;

++len;

if (cur->is_word) {

found = true;

break;

}

if (!ans.empty()) ans += ' ';

ans += found ? word.substr(0, len) : word;

}

return ans;

}

};

花花酱 LeetCode 929. Unique Email Addresses

By zxi on October 28, 2018

Every email consists of a local name and a domain name, separated by the @ sign.

For example, in alice@leetcode.com, alice is the local name, and leetcode.com is the domain name.

Besides lowercase letters, these emails may contain '.'s or '+'s.

If you add periods ('.') between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name. For example, "alice.z@leetcode.com" and "alicez@leetcode.com" forward to the same email address. (Note that this rule does not apply for domain names.)

If you add a plus ('+') in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered, for example m.y+name@email.com will be forwarded to my@email.com. (Again, this rule does not apply for domain names.)

It is possible to use both of these rules at the same time.

Given a list of emails, we send one email to each address in the list. How many different addresses actually receive mails?

Example 1:

Input: ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
Output: 2
Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails

Note:

1 <= emails[i].length <= 100
1 <= emails.length <= 100
Each emails[i] contains exactly one '@' character.

Solution:

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

C++

// Author: Huahua, 24 ms

class Solution {

public:

int numUniqueEmails(vector<string>& emails) {

unordered_set<string> s;

for (const string& email : emails) {

string e;

bool at = false;

bool plus = false;

for (char c : email) {

if (c == '.') {

if (!at) continue;

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

at = true;

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

if (!at) {

plus = true;

continue;

}

if (!at && plus) continue;

e += c;

}

s.insert(std::move(e));

}

return s.size();

}

};