Posts tagged as “trie”

花花酱 LeetCode 1707. Maximum XOR With an Element From Array

By zxi on December 27, 2020

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [x_i, m_i].

The answer to the i^th query is the maximum bitwise XOR value of x_i and any element of nums that does not exceed m_i. In other words, the answer is max(nums[j] XOR x_i) for all j such that nums[j] <= m_i. If all elements in nums are larger than m_i, then the answer is -1.

Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the i^th query.

Example 1:

Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]
Explanation:
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

Example 2:

Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
Output: [15,-1,5]

Constraints:

1 <= nums.length, queries.length <= 10⁵
queries[i].length == 2
0 <= nums[j], x_i, m_i <= 10⁹

Solution: Trie on the fly

We can build the trie on the fly by sorting nums in ascending order and queries by its limit, insert nums into the trie up the limit.

Time complexity: O(nlogn + QlogQ)
Space complexity: O(n)

C++

// Author: Huahua

class Trie {

public:

Trie(): children{nullptr, nullptr} {}

Trie* children[2];

};

class Solution {

public:

vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {

const int n = nums.size();

sort(begin(nums), end(nums));

const int Q = queries.size();

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

queries[i].push_back(i);

sort(begin(queries), end(queries), [](const auto& q1, const auto& q2) {

return q1[1] < q2[1];

});

Trie root;

auto insert = [&](int num) {

Trie* node = &root;

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (!node->children[bit])

node->children[bit] = new Trie();

node = node->children[bit];

}

};

auto query = [&](int num) {

Trie* node = &root;

int sum = 0;

for (int i = 31; i >= 0; --i) {

if (!node) return -1;

int bit = (num >> i) & 1;

if (node->children[1 - bit]) {

sum |= (1 << i);

node = node->children[1 - bit];

} else {

node = node->children[bit];

}

return sum;

};

vector<int> ans(Q);

int i = 0;

for (const auto& q : queries) {

while (i < n && nums[i] <= q[1]) insert(nums[i++]);

ans[q[2]] = query(q[0]);

}

return ans;

}

};

花花酱 LeetCode 421. Maximum XOR of Two Numbers in an Array

By zxi on December 27, 2020

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.

Follow up: Could you do this in O(n) runtime?

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [0]
Output: 0

Example 3:

Input: nums = [2,4]
Output: 6

Example 4:

Input: nums = [8,10,2]
Output: 10

Example 5:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Constraints:

1 <= nums.length <= 2 * 10⁴
0 <= nums[i] <= 2³¹ - 1

Solution: Trie

Time complexity: O(31*2*n)
Space complexity: O(31*2*n)

C++

// Author: Huahua

class Trie {

public:

Trie(): children(2) {}

vector<unique_ptr<Trie>> children;

};

class Solution {

public:

int findMaximumXOR(vector<int>& nums) {

Trie root;

// Insert a number into the trie.

auto insert = [&](Trie* node, int num) {

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (!node->children[bit])

node->children[bit] = std::make_unique<Trie>();

node = node->children[bit].get();

}

};

// Find max xor sum of num and another element in the array.

auto query = [&](Trie* node, int num) {

int sum = 0;

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (node->children[1 - bit]) {

sum += (1 << i);

node = node->children[1 - bit].get();

} else {

node = node->children[bit].get();

}

return sum;

};

// Insert all numbers.

for (int x : nums)

insert(&root, x);

int ans = 0;

// For each number find the maximum xor sum.

for (int x : nums)

ans = max(ans, query(&root, x));

return ans;

}

};

花花酱 LeetCode 1268. Search Suggestions System

By zxi on November 24, 2019

Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]

Example 2:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Example 3:

Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Example 4:

Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]

Constraints:

1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
All characters of products[i] are lower-case English letters.
1 <= searchWord.length <= 1000
All characters of searchWord are lower-case English letters.

Solution 1: Binary Search

Sort the input array and do two binary searches.
One for prefix of the search word as lower bound, another for prefix + ‘~’ as upper bound.
‘~’ > ‘z’

Time complexity: O(nlogn + l * logn)
Space complexity: O(1)

C++

// Author: Huahua, 36ms, 35MB

class Solution {

public:

vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {

vector<vector<string>> ans;

std::sort(begin(products), end(products));

string key;

for (char c : searchWord) {

key += c;

auto l = lower_bound(begin(products), end(products), key);

auto r = upper_bound(begin(products), end(products), key += '~');

if (l == r) break; // early return

key.pop_back();

ans.emplace_back(l, min(l + 3, r));

}

while (ans.size() != searchWord.length()) ans.push_back({});

return ans;

}

};

Solution 2: Trie

Initialization: Sum(len(products[i]))
Query: O(len(searchWord))

C++

// Author: Huahua, 148 ms, 98.8 MB

struct Trie {

Trie(): nodes(26) {}

~Trie() {

for (auto* node : nodes)

delete node;

}

vector<Trie*> nodes;

vector<const string*> words;

static void addWord(Trie* root, const string& word) {

for (char c : word) {

if (root->nodes[c - 'a'] == nullptr) root->nodes[c - 'a'] = new Trie();

root = root->nodes[c - 'a'];

if (root->words.size() < 3)

root->words.push_back(&word);

}

static vector<vector<string>> getWords(Trie* root, const string& prefix) {

vector<vector<string>> ans(prefix.size());

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

char c = prefix[i];

root = root->nodes[c - 'a'];

if (root == nullptr) break;

for (auto* word : root->words)

ans[i].push_back(*word);

}

return ans;

}

};

class Solution {

public:

vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {

std::sort(begin(products), end(products));

Trie root;

for (const auto& product : products)

Trie::addWord(&root, product);

return Trie::getWords(&root, searchWord);

}

};

花花酱 LeetCode 212. Word Search II

By zxi on August 20, 2019

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Note:

All inputs are consist of lowercase letters a-z.
The values of words are distinct.

Solution 1: DFS

Time complexity: O(sum(m*n*4^l))
Space complexity: O(l)

C++

// Author: Huahua, 708 ms, 15.3 MB

class Solution {

public:

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {

unordered_set<string> unique_words(words.begin(), words.end());

vector<string> ans;

for (const string& word : unique_words)

if (exist(board, word))

ans.push_back(word);

return ans;

}

private:

int w;

int h;

bool exist(vector<vector<char>> &board, string word) {

if (board.size() == 0) return false;

h = board.size();

w = board[0].size();

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

for (int j = 0 ; j < h; j++)

if (search(board, word, 0, i, j)) return true;

return false;

}

bool search(vector<vector<char>> &board,

const string& word, int d, int x, int y) {

if (x < 0 || x == w || y < 0 || y == h || word[d] != board[y][x])

return false;

// Found the last char of the word

if (d == word.length() - 1)

return true;

char cur = board[y][x];

board[y][x] = '#';

bool found = search(board, word, d + 1, x + 1, y)

|| search(board, word, d + 1, x - 1, y)

|| search(board, word, d + 1, x, y + 1)

|| search(board, word, d + 1, x, y - 1);

board[y][x] = cur;

return found;

}

};

Solution 2: Trie

Store all the words into a trie, search the board using DFS, paths must be in the trie otherwise there is no need to explore.

Time complexity: O(sum(l) + 4^max(l))
space complexity: O(sum(l) + l)

C++

// Author: Huahua, 64 ms, 35.6 MB

class TrieNode {

public:

vector<TrieNode*> nodes;

const string* word;

TrieNode(): nodes(26), word(nullptr) {}

~TrieNode() {

for (auto node : nodes) delete node;

}

};

class Solution {

public:

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {

TrieNode root;

// Add all the words into Trie.

for (const string& word : words) {

TrieNode* cur = &root;

for (char c : word) {

auto& next = cur->nodes[c - 'a'];

if (!next) next = new TrieNode();

cur = next;

}

cur->word = &word;

}

const int n = board.size();

const int m = board[0].size();

vector<string> ans;

function<void(int, int, TrieNode*)> walk = [&](int x, int y, TrieNode* node) {

if (x < 0 || x == m || y < 0 || y == n || board[y][x] == '#')

return;

const char cur = board[y][x];

TrieNode* next_node = node->nodes[cur - 'a'];

// Pruning, only expend paths that are in the trie.

if (!next_node) return;

if (next_node->word) {

ans.push_back(*next_node->word);

next_node->word = nullptr;

}

board[y][x] = '#';

walk(x + 1, y, next_node);

walk(x - 1, y, next_node);

walk(x, y + 1, next_node);

walk(x, y - 1, next_node);

board[y][x] = cur;

};

// Try all possible pathes.

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

for (int j = 0 ; j < m; j++)

walk(j, i, &root);

return ans;

}

};

花花酱 LeetCode Weekly Contest 133

By zxi on April 20, 2019

LeetCode 1029 Two City Scheduling

Solution1: DP

dp[i][j] := min cost to put j people into city A for the first i people
dp[0][0] = 0
dp[i][0] = dp[i -1][0] + cost_b
dp[i][j] = min(dp[i – 1][j] + cost_b, dp[i – 1][j – 1] + cost_a)
ans := dp[n][n/2]

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

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int twoCitySchedCost(vector<vector<int>>& costs) {

int n = costs.size();

vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX / 2));

dp[0][0] = 0;

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

dp[i][0] = dp[i - 1][0] + costs[i - 1][1];

for (int j = 1; j <= i; ++j)

dp[i][j] = min(dp[i - 1][j - 1] + costs[i - 1][0],

dp[i - 1][j] + costs[i - 1][1]);

}

return dp[n][n / 2];

}

};

Solution 2: Greedy

Sort by cost_a – cost_b

Choose the first n/2 people for A, rest for B

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

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int twoCitySchedCost(vector<vector<int>>& costs) {

int n = costs.size();

sort(begin(costs), end(costs), [](const auto& c1, const auto& c2){

return c1[0] - c1[1] < c2[0] - c2[1];

});

int ans = 0;

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

ans += i < n/2 ? costs[i][0] : costs[i][1];

return ans;

}

};

1030. Matrix Cells in Distance Order

Solution: Sorting

Time complexity: O(RC*log(RC))
Space complexity: O(RC)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {

vector<vector<int>> ans;

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

for (int j = 0; j < C; ++j)

ans.push_back({i, j});

std::sort(begin(ans), end(ans), [r0, c0](const vector<int>& a, const vector<int>& b){

return (abs(a[0] - r0) + abs(a[1] - c0)) < (abs(b[0] - r0) + abs(b[1] - c0));

});

return ans;

}

};

1031. Maximum Sum of Two Non-Overlapping Subarrays

Solution: Prefix sum

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

C++

// Author: Huahua

class Solution {

public:

int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {

const int n = A.size();

vector<int> s(n + 1, 0);

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

s[i + 1] = s[i] + A[i];

int ans = 0;

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

int ls = s[i + L] - s[i];

int ms = max(maxSum(s, 0, i - M - 1, M),

maxSum(s, i + L, n - M, M));

ans = max(ans, ls + ms);

}

return ans;

}

private:

int maxSum(const vector<int>& s, int start, int end, int l) {

int ans = INT_MIN;

for (int i = start; i <= end; ++i)

ans = max(ans, s[i + l] - s[i]);

return ans;

}

};

1032. Stream of Characters

Solution: Trie

Time complexity:

build O(sum(len(w))
query O(max(len(w))

Space complexity: O(sum(len(w))

C++

// Author: Huahua, 320 ms, 95 MB

class TrieNode {

public:

~TrieNode() {

for (auto node : next_)

delete node;

}

void reverse_build(const string& s, int i) {

if (i == -1) {

is_word_ = true;

return;

}

const int idx = s[i] - 'a';

if (!next_[idx]) next_[idx] = new TrieNode();

next_[idx]->reverse_build(s, i - 1);

}

bool reverse_search(const string& s, int i) {

if (i == -1 || is_word_) return is_word_;

const int idx = s[i] - 'a';

if (!next_[idx]) return false;

return next_[idx]->reverse_search(s, i - 1);

}

private:

bool is_word_ = false;

TrieNode* next_[26] = {0};

};

class StreamChecker {

public:

StreamChecker(vector<string>& words) {

root_ = std::make_unique<TrieNode>();

for (const string& w : words)

root_->reverse_build(w, w.length() - 1);

}

bool query(char letter) {

s_ += letter;

return root_->reverse_search(s_, s_.length() - 1);

}

private:

string s_;

unique_ptr<TrieNode> root_;

};

Java

// Author: Huahua, running time: 133 ms

class StreamChecker {

class TrieNode {

public TrieNode() {

isWord = false;

next = new TrieNode[26];

}

public boolean isWord;

public TrieNode next[];

}

private TrieNode root;

private StringBuilder sb;

public StreamChecker(String[] words) {

root = new TrieNode();

sb = new StringBuilder();

for (String word : words) {

TrieNode node = root;

char[] w = word.toCharArray();

for (int i = w.length - 1; i >= 0; --i) {

int idx = w[i] - 'a';

if (node.next[idx] == null) node.next[idx] = new TrieNode();

node = node.next[idx];

}

node.isWord = true;

}

public boolean query(char letter) {

sb.append(letter);

TrieNode node = root;

for (int i = sb.length() - 1; i >= 0; --i) {

int idx = sb.charAt(i) - 'a';

if (node.next[idx] == null) return false;

if (node.next[idx].isWord) return true;

node = node.next[idx];

}

return false;

}