Model: Sid-the-sloth/leetcode_unixcoder_final
Author: Sid-the-sloth
Pipeline: feature-extraction
Library: sentence-transformers
Tags: sentence-transformers, safetensors, roberta, sentence-similarity, feature-extraction, dense, generated_from_trainer, dataset_size:4088, loss:CoSENTLoss, en, arxiv:1908.10084, base_model:microsoft/unixcoder-base, base_model:finetune:microsoft/unixcoder-base, license:mit, model-index, text-embeddings-inference, endpoints_compatible, region:us
Base models (finetune): id: microsoft/unixcoder-base
Card metadata: tags: sentence-transformers, sentence-similarity, feature-extraction, dense, generated_from_trainer, dataset_size:4088, loss:CoSENTLoss
base_model: microsoft/unixcoder-base
widget: source_sentence: Name: Split BST | Code: // Time:  O(n)
// Space: O(h)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> splitBST(TreeNode* root, int V) {
        if (!root) {
            return {nullptr, nullptr};
        } else if (root->val <= V) {
            const auto& result = splitBST(root->right, V);
            root->right = result[0];
            return {root, result[1]};
        } else {
            const auto& result = splitBST(root->left, V);
            root->left = result[1];
            return {result[0], root};
        }
    }
};
 | Tags: Binary Search Tree,Binary Tree,Recursion,Tree
sentences: Name: Parallel Courses III | Code: // Time:  O(|V| + |E|)
// Space: O(|E|)

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        vector<vector<int>> adj(n);
        vector<int> in_degree(n);
        for (const auto& relation : relations) {
            adj[relation[0] - 1].emplace_back(relation[1] - 1);
            ++in_degree[relation[1] - 1];
        }
        vector<int> q;
        vector<int> dist(n);
        for (int u = 0; u < n; ++u) {
            if (in_degree[u]) {
                continue;
            }
            q.emplace_back(u);
            dist[u] = time[u];
        }
        while (!empty(q)) {
            vector<int> new_q;
            for (const auto& u : q) {
                for (const auto& v : adj[u]) {
                    dist[v] = max(dist[v], dist[u] + time[v]);
                    --in_degree[v];
                    if (!in_degree[v]) {
                        new_q.emplace_back(v);
                    }
                }
            }
            q = move(new_q);
        }
        return *max_element(cbegin(dist), cend(dist));
    }
};
 | Tags: Array,Dynamic Programming,Graph,Topological Sort, Name: Determine Whether Matrix Can Be Obtained By Rotation | Code: // Time:  O(m * n)
// Space: O(1)

class Solution {
public:
    bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
        vector<function<bool (int, int)>> checks = {
            [&mat, &target](int i, int j) { return mat[i][j] == target[i][j]; },
            [&mat, &target](int i, int j) { return mat[i][j] == target[j][size(mat) - 1 - i]; },
            [&mat, &target](int i, int j) { return mat[i][j] == target[size(mat) - 1 - i][size(mat[0]) - 1 - j]; },
            [&mat, &target](int i, int j) { return mat[i][j] == target[size(mat[0]) - 1 - j][i]; },
        };
        const auto& traverse = [&mat, &target](const auto& check) {
            for (int i = 0; i < size(mat); ++i) {
                for (int j = 0; j < size(mat[0]); ++j) {
                    if (!check(i, j)) {
                        return false;
                    }
                }
            }
            return true;
        };
        for (const auto& check : checks) {
            if (traverse(check)) {
                return true;
            }
        }
        return false;
    }
};
 | Tags: Array,Matrix, Name: Maximum Total Reward Using Operations I | Code: // Time:  O(nlogn + r^2), r = max(rewardValues)
// Space: O(r)

// sort, dp, bitset
class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        static const int MAX_VALUE = 20000;

        unordered_set<int> v_set(cbegin(rewardValues), cend(rewardValues));
        vector<int> sorted_v(cbegin(v_set), cend(v_set));
        sort(begin(sorted_v), end(sorted_v));
        bitset<(MAX_VALUE - 1) + 1> dp, mask;
        dp[0] = true;
        int i = 0;
        for (int i = 0, j = 0; i + 1 < size(sorted_v); ++i) {
            while (j < sorted_v[i]) {
                mask[j++] = true;
            }
            dp |= (dp & mask) << sorted_v[i];
        }
        int result = sorted_v.back() - 1;
        for (; !dp[result]; --result);
        return sorted_v.back() + result;
    }
};

// Time:  O(nlogn + r^2), r = max(rewardValues)
// Space: O(r)
// sort, dp, bitset
class Solution2 {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        static const int MAX_VALUE = 20000;

        unordered_set<int> v_set(cbegin(rewardValues), cend(rewardValues));
        vector<int> sorted_v(cbegin(v_set), cend(v_set));
        sort(begin(sorted_v), end(sorted_v));
        bitset<(MAX_VALUE * 2 - 1) + 1> dp, mask;
        dp[0] = true;
        int i = 0;
        for (int i = 0, j = 0; i < size(sorted_v); ++i) {
            while (j < sorted_v[i]) {
                mask[j++] = true;
            }
            dp |= (dp & mask) << sorted_v[i];
        }
        int result = 2 * sorted_v.back() - 1;
        for (; !dp[result]; --result);
        return result;
    }
};

// Time:  O(nlogn + r^2), r = max(rewardValues)
// Space: O(r)
// sort, dp
class Solution3 {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        unordered_set<int> v_set(cbegin(rewardValues), cend(rewardValues));
        vector<int> sorted_v(cbegin(v_set), cend(v_set));
        sort(begin(sorted_v), end(sorted_v));
        const int mx = sorted_v.back();
        vector<bool> dp((mx - 1) + 1);
        dp[0] = true;
        for (int i = 0; i + 1 < size(sorted_v); ++i) {
            for (int x = 0; x < min(sorted_v[i], mx - sorted_v[i]); ++x) {
                if (dp[x]) {
                    dp[sorted_v[i] + x] = dp[x];
                }
            }
        }
        int result = mx - 1;
        for (; !dp[result]; --result);
        return mx + result;
    }
};

// Time:  O(nlogn + r^2), r = max(rewardValues)
// Space: O(r)
// sort, dp
class Solution4 {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        unordered_set<int> v_set(cbegin(rewardValues), cend(rewardValues));
        vector<int> sorted_v(cbegin(v_set), cend(v_set));
        sort(begin(sorted_v), end(sorted_v));
        const int mx = sorted_v.back();
        vector<bool> dp((mx * 2 - 1) + 1);
        dp[0] = true;
        for (int i = 0; i < size(sorted_v); ++i) {
            for (int x = 0; x < sorted_v[i]; ++x) {
                if (dp[x]) {
                    dp[sorted_v[i] + x] = dp[x];
                }
            }
        }
        int result = 2 * mx - 1;
        for (; !dp[result]; --result);
        return result;
    }
};
 | Tags: Array,Dynamic Programming, source_sentence: Name: Valid Perfect Square | Code: // Time:  O(logn)
// Space: O(1)

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left = 1, right = num;
        while (left <= right) {
            const int mid = left + (right - left) / 2;
            if (mid >= num / mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left == num / left && num % left == 0;
    }
};
 | Tags: Binary Search,Math
sentences: Name: Shortest Bridge | Code: // Time:  O(n^2)
// Space: O(n^2)

class Solution {
public:
    template <typename T>
    struct PairHash {
        size_t operator()(const pair<T, T>& p) const {
            size_t seed = 0;
            seed ^= std::hash<T>{}(p.first)  + 0x9e3779b9 + (seed<<6) + (seed>>2);
            seed ^= std::hash<T>{}(p.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
            return seed;
        }
    };
    
    int shortestBridge(vector<vector<int>>& A) {
        static const vector<pair<int, int>> directions{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        unordered_set<pair<int, int>, PairHash<int>> lookup;
        unordered_set<pair<int, int>, PairHash<int>> target;
        auto islands = get_islands(A);
        lookup = move(islands[0]);
        target = move(islands[1]);
        queue<pair<pair<int, int>, int>> q;
        for (const auto& node : lookup) {
            q.emplace(node, 0);
        }
        while (!q.empty()) {
            pair<int, int> node;
            int dis;
            tie(node, dis) = q.front(); q.pop();
            if (target.count(node)) {
                return dis - 1;
            }
            for (const auto& d : directions) {
                pair<int, int> nei = make_pair(node.first + d.first, node.second + d.second);
                if (0 > nei.first || nei.first >= A.size() ||
                    0 > nei.second || nei.second >= A[0].size() ||
                    lookup.count(nei)) {
                    continue;
                }
                q.emplace(nei, dis + 1);
                lookup.emplace(nei);
            }
        }
    }

private:
    vector<unordered_set<pair<int, int>, PairHash<int>>> get_islands(const vector<vector<int>>& A) {
        static const vector<pair<int, int>> directions{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        vector<unordered_set<pair<int, int>, PairHash<int>>> islands;
        unordered_set<pair<int, int>, PairHash<int>> done;
        for (int r = 0; r < A.size(); ++r) {
            for (int c = 0; c < A[0].size(); ++c) {
                if (A[r][c] == 0 || done.count(make_pair(r, c))) {
                    continue;
                }
                vector<pair<int, int>> s{{r, c}};
                unordered_set<pair<int, int>, PairHash<int>> lookup(s.cbegin(), s.cend());
                while (!s.empty()) {
                    auto node = s.back(); s.pop_back();
                    for (const auto& d : directions) {
                        pair<int, int> nei = make_pair(node.first + d.first, node.second + d.second);
                        if (0 > nei.first || nei.first >= A.size() ||
                            0 > nei.second || nei.second >= A[0].size() ||
                            lookup.count(nei) || A[nei.first][nei.second] == 0) {
                            continue;
                        }
                        s.emplace_back(nei);
                        lookup.emplace(nei);
                    }
                }
                for (const auto& node : lookup) {
                    done.emplace(node);
                }
                islands.emplace_back(move(lookup));
                if (islands.size() == 2) {
                    break;
                }
            }
        }
        return islands;
    }
};
 | Tags: Array,Breadth-First Search,Depth-First Search,Matrix, Name: Merge Two Binary Trees | Code: // Time:  O(n)
// Space: O(h)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (!t1) {
            return t2;
        }
        if (!t2) {
            return t1;
        }
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
};
 | Tags: Binary Tree,Breadth-First Search,Depth-First Search,Tree, Name: Sum of Square Numbers | Code: // Time:  O(sqrt(c) * logc)
// Space: O(1)

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (long long a = 0; a * a <= c; ++a) {
            auto b = static_cast<int>(sqrt(c - a * a));
            if (a * a + b * b == c) {
                return true;
            }
        }
        return false;
    }
};

 | Tags: Binary Search,Math,Two Pointers, source_sentence: Name: Count Paths That Can Form a Palindrome in a Tree | Code: // Time:  O(n)
// Space: O(n)

// iterative dfs, freq table
class Solution {
public:
    long long countPalindromePaths(vector<int>& parent, string s) {
        unordered_map<int, int> cnt;
        cnt[0] = 1;
        vector<vector<int>> adj(size(parent));
        for (int u = 0; u < size(parent); ++u) {
            if (parent[u] != -1) {
                adj[parent[u]].emplace_back(u);
            }
        }
        const auto& iter_dfs = [&]() {
            int64_t result = 0;
            vector<pair<int, int>> stk = {{0, 0}};
            while (!empty(stk)) {
                auto [u, mask] = stk.back(); stk.pop_back();
                if (u) {
                    mask ^= 1 << (s[u] - 'a');
                    for (int i = 0; i < 26; ++i) {
                        if (cnt.count(mask ^ (1 << i))) {
                            result += cnt[mask ^ (1 << i)];
                        }
                    }
                    result += cnt[mask]++;
                }
                for (const auto& v : adj[u]) {
                    stk.emplace_back(v, mask);
                }
            }
            return result;
        };
        return iter_dfs();
    }
};

// Time:  O(n)
// Space: O(n)
// dfs, freq table
class Solution2 {
public:
    long long countPalindromePaths(vector<int>& parent, string s) {
        unordered_map<int, int> cnt;
        cnt[0] = 1;
        vector<vector<int>> adj(size(parent));
        for (int u = 0; u < size(parent); ++u) {
            if (parent[u] != -1) {
                adj[parent[u]].emplace_back(u);
            }
        }
        const function<int64_t (int, int)> dfs = [&](int u, int mask) {
            int64_t result = 0;
            if (u) {
                mask ^= 1 << (s[u] - 'a');
                for (int i = 0; i < 26; ++i) {
                    if (cnt.count(mask ^ (1 << i))) {
                        result += cnt[mask ^ (1 << i)];
                    }
                }
                result += cnt[mask]++;
            }
            for (const auto& v : adj[u]) {
                result += dfs(v, mask);
            }
            return result;
        };
        return dfs(0, 0);
    }
};
 | Tags: Bit Manipulation,Bitmask,Depth-First Search,Dynamic Programming,Tree
sentences: Name: Recover a Tree From Preorder Traversal | Code: // Time:  O(n)
// Space: O(h)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// iterative stack solution
class Solution {
public:
    TreeNode* recoverFromPreorder(string S) {
        int i = 0;
        vector<TreeNode *> stack;
        while (i < S.length()) {
            int j = S.find_first_not_of("-", i);
            int level = j - i;
            i = j;
            while (stack.size() > level) {
                stack.pop_back();
            }
            j = S.find_first_of("-", i);
            auto node = new TreeNode(stoi(S.substr(i, j - i)));
            i = j;
            if (!stack.empty()) {
                if (!stack.back()->left) {
                    stack.back()->left = node;
                } else{
                    stack.back()->right = node;
                }
            }
            stack.emplace_back(node);
        }
        return stack.front();
    }
};

// Time:  O(n)
// Space: O(h)
// recursive solution
class Solution2 {
public:
    TreeNode* recoverFromPreorder(string S) {
        int i = 0;
        return recoverFromPreorderHelper(S, 0, &i);
    }

private:
    TreeNode* recoverFromPreorderHelper(const string& S, int level, int *i) {
        int j = S.find_first_not_of("-", *i);
        if (level != j - *i) {
            return nullptr;
        }
        *i = j;
        j = S.find_first_of("-", *i);
        auto node = new TreeNode(stoi(S.substr(*i, j - *i)));
        *i = j;
        node->left = recoverFromPreorderHelper(S, level + 1, i);
        node->right = recoverFromPreorderHelper(S, level + 1, i);
        return node;
    }
};
 | Tags: Binary Tree,Depth-First Search,String,Tree, Name: Separate the Digits in an Array | Code: // Time:  O(n * logr)
// Space: O(1)

// array
class Solution {
public:
    vector<int> separateDigits(vector<int>& nums) {
        vector<int> result;
        for (int i = size(nums) - 1; i >= 0; --i) {
            for (int x = nums[i]; x; x /= 10) {
                result.emplace_back(x % 10);
            }
        }
        reverse(begin(result), end(result));
        return result;
    }
};

// Time:  O(n * logr)
// Space: O(logr), r = max(nums)
// array
class Solution2 {
public:
    vector<int> separateDigits(vector<int>& nums) {
        vector<int> result;
        for (const auto& x : nums) {
            for (const auto& c : to_string(x)) {
                result.emplace_back(c - '0');
            }
        }
        return result;
    }
};
 | Tags: Array,Simulation, Name: Strobogrammatic Number II | Code: // Time:  O(n * 5^(n/2))
// Space: O(n)

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        static const unordered_map<string, string> lookup{{"0", "0"}, {"1", "1"},
                                                          {"6", "9"}, {"8", "8"}, 
                                                          {"9", "6"}};
        vector<string> result = {""};
        if (n % 2) {
            result = {"0", "1", "8"};
        }
        for (int i = n % 2; i < n; i += 2) {
            vector<string> new_result;
            for (const auto& num : result) {
                for (const auto& [a, b] : lookup) {
                    if (i != n - 2 || a != "0") {
                        new_result.emplace_back(a + num + b);
                    }
                }
            }
            result = move(new_result);
        }
        return result;
    }
};

// Time:  O(n * 5^(n/2))
// Space: O(n)
class Solution2 {
public:
    vector<string> findStrobogrammatic(int n) {
        return findStrobogrammaticRecu(n, n);
    }

private:
    vector<string> findStrobogrammaticRecu(const int n, int k) {
        static const unordered_map<string, string> lookup{{"0", "0"}, {"1", "1"},
                                                          {"6", "9"}, {"8", "8"}, 
                                                          {"9", "6"}};
        if (k == 0) {
            return {""};
        } else if (k == 1) {
            return {"0", "1", "8"};
        }
        vector<string> result;
        for (const auto& num : findStrobogrammaticRecu(n, k - 2)) {
            for (const auto& kvp : lookup) {
                if (n != k || kvp.first != "0") {
                    result.emplace_back(kvp.first + num + kvp.second);
                }
            }
        }
        return result;
    }
};
 | Tags: Array,Recursion,String, source_sentence: Name: Most Frequent IDs | Code: // Time:  O(nlogn)
// Space: O(n)

// heap
class Solution {
public:
    vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {
        vector<long long> result;
        unordered_map<int, int64_t> cnt;
        priority_queue<pair<int64_t, int>> max_heap;
        for (int i = 0; i < size(nums); ++i) {
            cnt[nums[i]] += freq[i];
            max_heap.emplace(cnt[nums[i]], nums[i]);
            while (!empty(max_heap) && max_heap.top().first != cnt[max_heap.top().second]) {
                max_heap.pop();
            }
            result.emplace_back(!empty(max_heap) ? max_heap.top().first : 0);
        }
        return result;
    }
};

// Time:  O(nlogn)
// Space: O(n)
// bst
class Solution2 {
public:
    vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {
        vector<long long> result;
        unordered_map<int, int64_t> cnt;
        map<int64_t, int> bst;
        for (int i = 0; i < size(nums); ++i) {
            if (--bst[cnt[nums[i]]] == 0) {
                bst.erase(cnt[nums[i]]);
            }
            cnt[nums[i]] += freq[i];
            ++bst[cnt[nums[i]]];
            result.emplace_back(rbegin(bst)->first);
        }
        return result;
    }
};
 | Tags: Array,Hash Table,Heap (Priority Queue),Ordered Set
sentences: Name: Design HashSet | Code: // Time:  O(1)
// Space: O(n)

class MyHashSet {
public:
    /** Initialize your data structure here. */
    MyHashSet() : data_(10000) {
        
    }
    
    void add(int key) {
        auto& list = data_[key % data_.size()];
        auto it = find(list.begin(), list.end(), key);
        if (it == list.end()) {
            list.emplace_back(key);
        }
    }
    
    void remove(int key) {
        auto& list = data_[key % data_.size()];
        auto it = find(list.begin(), list.end(), key);
        if (it != list.end()) {
            list.erase(it);
        }
    }
    
    /** Returns true if this set did not already contain the specified element */
    bool contains(int key) {
        auto& list = data_[key % data_.size()];
        auto it = find(list.begin(), list.end(), key);
        return it != list.end();
    }

private:
    vector<list<int>> data_;
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * bool param_3 = obj.contains(key);
 */
 
 | Tags: Array,Design,Hash Function,Hash Table,Linked List, Name: Max Area of Island | Code: // Time:  O(m * n)
// Space: O(m * n), the max depth of dfs may be m * n

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int result = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                int area = 0;
                if (dfs(i, j, &grid, &area)) {
                    result = max(result, area);
                }
            }
        }
        return result;
    }

private:
    bool dfs(const int i, const int j, vector<vector<int>> *grid, int *area) {
        static const vector<pair<int, int>> directions{{-1,  0}, { 1,  0},
                                                       { 0,  1}, { 0, -1}};
        if (i < 0 || i >= grid->size() ||
            j < 0 || j >= (*grid)[0].size() ||
            (*grid)[i][j] <= 0) {
            return false;
        }
        (*grid)[i][j] *= -1;
        ++(*area);
        for (const auto& d : directions) {
            dfs(i + d.first, j + d.second, grid, area);
        }
        return true;
    }
};
 | Tags: Array,Breadth-First Search,Depth-First Search,Matrix,Union Find, Name: Stone Game VII | Code: // Time:  O(n^2)
// Space: O(n)

class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        vector<int> prefix(1);
        for (const auto& stone : stones) {
            prefix.emplace_back(prefix.back() + stone);
        }
        const auto& score = [&prefix](int i, int j) {
            return prefix[j + 1] - prefix[i];
        };
        vector<vector<int>> dp(2, vector<int>(size(stones)));
        for (int i = size(stones) - 1; i >= 0; --i) {
            for (int j = i + 1; j < size(stones); ++j) {
                dp[i % 2][j] = max(score(i + 1, j) - dp[(i + 1) % 2][j],
                                   score(i, j - 1) - dp[i % 2][j - 1]);
            }
        }
        return dp[0][size(stones) - 1];
    }
};
 | Tags: Array,Dynamic Programming,Game Theory,Math, source_sentence: Name: Arithmetic Slices | Code: // Time:  O(n)
// Space: O(1)

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int res = 0, i = 0;
        for (int i = 0; i + 2 < A.size(); ++i) {
            const auto start = i;
            while (i + 2 < A.size() && A[i + 2] + A[i] == 2 * A[i + 1]) {
                res += (i++) - start + 1;
            }
        }
        return res;
    }
};
 | Tags: Array,Dynamic Programming,Sliding Window
sentences: Name: Prefix and Suffix Search | Code: // Time:  ctor:   O(w * l^2), w is the number of words, l is the word length on average
//        search: O(p + s)  , p is the length of the prefix, s is the length of the suffix,
// Space: O(t), t is the number of trie nodes

class WordFilter {
public:
    WordFilter(vector<string> words) {
        for (int i = 0; i < words.size(); ++i) {
            for (int j = 0; j <= words[i].length(); ++j) {
                trie_.insert(words[i].substr(j) + SEPARATOR + words[i], i);
            }
        }
    }
    
    int f(string prefix, string suffix) {
        return trie_.find(suffix + SEPARATOR + prefix);
    }

private:
    struct TrieNode {
        int weight;
        vector<TrieNode *> leaves;

        TrieNode() : weight(0), leaves(27) {}

        void insert(const string& s, const int weight) {
            auto* p = this;
            p->weight = weight;
            for (const auto& c : s) {
                if (!p->leaves[c - 'a']) {
                    p->leaves[c - 'a'] = new TrieNode;
                }
                p = p->leaves[c - 'a'];
                p->weight = weight;
            }
        }

        int find(const string& s) const {
            auto* p = this;
            for (const auto& c : s) {
                if (!p->leaves[c - 'a']) {
                    return -1;
                }
                p = p->leaves[c - 'a'];
            }
            return p->weight;
        }

        ~TrieNode() {
            for (auto& node : leaves) {
                if (node) {
                    delete node;
                }
            }
        }
    };
    const string SEPARATOR = "{";  // ascii code of 'z' + 1
    TrieNode trie_;
};

// Time:  ctor:   O(w * l), w is the number of words, l is the word length on average
//        search: O(p + s + max(m, n)), p is the length of the prefix, s is the length of the suffix,
//                                      m is the number of the prefix match, n is the number of the suffix match
// Space: O(w * l)
class WordFilter2 {
public:
    WordFilter(vector<string> words) {
        for (int i = words.size() - 1; i >= 0; --i) {
            auto word = words[i];
            prefix_trie_.insert(word, i);
            reverse(word.begin(), word.end());
            suffix_trie_.insert(word, i);
        }
    }
    
    int f(string prefix, string suffix) {
        const auto& prefix_match = prefix_trie_.find(prefix);
        reverse(suffix.begin(), suffix.end());
        const auto& suffix_match = suffix_trie_.find(suffix);
        int i = 0, j = 0;
        while (i != prefix_match.size() && j != suffix_match.size()) {
            if (prefix_match[i] == suffix_match[j]) {
                return prefix_match[i];
            } else if (prefix_match[i] > suffix_match[j]) {
                ++i;
            } else {
                ++j;
            }
        }
        return -1;
    }
    
private:
    struct TrieNode {
        vector<int> words; // index of words
        vector<TrieNode *> leaves;

        TrieNode() : leaves(26) {}

        void insert(const string& s, const int i) {
            auto* p = this;
            p->words.emplace_back(i);
            for (const auto& c : s) {
                if (!p->leaves[c - 'a']) {
                    p->leaves[c - 'a'] = new TrieNode;
                }
                p = p->leaves[c - 'a'];
                p->words.emplace_back(i);
            }
        }

        const vector<int>& find(const string& s) const {
            auto* p = this;
            for (const auto& c : s) {
                if (!p->leaves[c - 'a']) {
                    static const vector<int> empty;
                    return empty;
                }
                p = p->leaves[c - 'a'];
            }
            return p->words;
        }

        ~TrieNode() {
            for (auto& node : leaves) {
                if (node) {
                    delete node;
                }
            }
        }
    };
    TrieNode prefix_trie_, suffix_trie_;
};

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(prefix,suffix);
 */
 | Tags: Array,Design,Hash Table,String,Trie, Name: Reverse Odd Levels of Binary Tree | Code: // Time:  O(n)
// Space: O(n)

// bfs
class Solution {
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        vector<TreeNode*> q = {root};
        for (int parity = 0; !empty(q); parity ^= 1) {
            if (parity) {
                for (int left = 0, right = size(q) - 1; left < right; ++left, --right) {
                    swap(q[left]->val, q[right]->val);
                }
            }
            if (!q[0]->left) {
                break;
            }
            vector<TreeNode*> new_q;
            for (const auto& node : q) {
                new_q.emplace_back(node->left);
                new_q.emplace_back(node->right);
            }
            q = move(new_q);
        }
        return root;
    }
};
 | Tags: Binary Tree,Breadth-First Search,Depth-First Search,Tree, Name: Arithmetic Subarrays | Code: // Time:  O(n * q)
// Space: O(n)

class Solution {
public:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        vector<bool> result(size(l));
        for (int i = 0; i < size(l); ++i) {
            result[i] = isArith(vector<int>(cbegin(nums) + l[i], cbegin(nums) + r[i] + 1));
        }
        return result;
    }

private:
    bool isArith(const vector<int>& nums) {
        unordered_set<int> lookup(cbegin(nums), cend(nums));
        int mn = *min_element(cbegin(nums), cend(nums));
        int mx = *max_element(cbegin(nums), cend(nums));
        if (mx == mn) {
            return true;
        }
        if ((mx - mn) % (size(nums) - 1)) {
            return false;
        }
        int d = (mx - mn) / (size(nums) - 1);
        for (int i = mn; i <= mx; i += d) {
            if (!lookup.count(i)) {
                return false;
            }
        }
        return true;
    }
};
 | Tags: Array,Hash Table,Sorting
pipeline_tag: feature-extraction
library_name: sentence-transformers
metrics: pearson_cosine, spearman_cosine
model-index: name: SentenceTransformer based on microsoft/unixcoder-base
results: task: type: semantic-similarity
name: Semantic Similarity
dataset: name: unixcoder leetcode eval
type: unixcoder_leetcode_eval
metrics: type: pearson_cosine
value: 0.8844784116914098
name: Pearson Cosine
verified: no, type: spearman_cosine
value: 0.8840382708528214
name: Spearman Cosine
verified: no
license: mit
language: en
Likes: 0 | All-time downloads: 13
Created: 2025-08-28 07:23:40