844. Backspace String Compare

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:

1. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S and T only contain lowercase letters and '#' characters.

Follow up:

• Can you solve it in O(N) time and O(1) space?

class Solution {

public:

    string process (string S) {

        int i = 0, j = 0;

        while (i < S.size()) {

            if (S[i] == '#') {

                if (j > 0) {

                    j--;

                }

                i++;

            } else {

                S[j++] = S[i++];

            }

        }

        if (j == S.size()) {

            return S;

        }

        return S.substr(0, j);

    }

    bool backspaceCompare(string S, string T) {

        if (S == T) {

            return true;

        }

        return process(S) == process(T);

    }

};

359. Logger Rate Limiter

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

It is possible that several messages arrive roughly at the same time.

Example:

Logger logger = new Logger();

// logging string "foo" at timestamp 1
logger.shouldPrintMessage(1, "foo"); returns true; 

// logging string "bar" at timestamp 2
logger.shouldPrintMessage(2,"bar"); returns true;

// logging string "foo" at timestamp 3
logger.shouldPrintMessage(3,"foo"); returns false;

// logging string "bar" at timestamp 8
logger.shouldPrintMessage(8,"bar"); returns false;

// logging string "foo" at timestamp 10
logger.shouldPrintMessage(10,"foo"); returns false;

// logging string "foo" at timestamp 11
logger.shouldPrintMessage(11,"foo"); returns true;

class Logger {
private:
    unordered_map<string, int> mp;
public:
    /** Initialize your data structure here. */
    Logger() {
       
    }
   
    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    bool shouldPrintMessage(int timestamp, string message) {
        if (mp.find(message)) {
            mp[message] = timestamp;
            return true;
        }

        if (timestamp - mp[message] < 10) {
            return false;
        }
        mp[message] = timestamp;
        return true;
    }
};

/**
 * Your Logger object will be instantiated and called as such:
 * Logger* obj = new Logger();
 * bool param_1 = obj->shouldPrintMessage(timestamp,message);
 */

951. Flip Equivalent Binary Trees

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.

A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.

Write a function that determines whether two binary trees are flip equivalent.  The trees are given by root nodes root1 and root2.

Example 1:

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explanation: We flipped at nodes with values 1, 3, and 5.

Note:

1. Each tree will have at most 100 nodes.
2. Each value in each tree will be a unique integer in the range [0, 99].

class Solution {

public:

    bool flipEquiv(TreeNode* root1, TreeNode* root2) {

        if (root1 == NULL) {

            return root2 == NULL;

        }

        if (root2 == NULL) {

            return root1 == NULL;

        }

        if (root1 -> val != root2 -> val) {

            return false;

        }

        return (flipEquiv(root1 -> left, root2 -> left) && flipEquiv(root1 -> right, root2 -> right)) || (flipEquiv(root1 -> left, root2 -> right) && flipEquiv(root1 -> right, root2 -> left));

        

    }

};

===== BFS =====

bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        
        queue<TreeNode*> q1; 
        queue<TreeNode*> q2; 
        
        if(root1) q1.push(root1); 
        if(root2) q2.push(root2); 
        
        while(!q1.empty() && !q2.empty()){
            TreeNode* cur1 = q1.front(); 
            TreeNode* cur2 = q2.front(); 
        
            //cout << cur1->val << " :" << cur2->val  <<endl ; 
            if(cur1->val != cur2->val) return false; 
            
            if(cur1->left) q1.push(cur1->left);
            if(cur1->right) q1.push(cur1->right);
                
            if(cur1->left && cur2->left && cur1->left->val == cur2->left->val)
                q2.push(cur2->left);
            else if(cur1->left && cur2->right && cur1->left->val == cur2->right->val)
                q2.push(cur2->right);
            
            if(cur1->right&& cur2->right && cur1->right->val == cur2->right->val)
                q2.push(cur2->right);
            else if(cur1->right && cur2->left && cur1->right->val == cur2->left->val)
                q2.push(cur2->left);    
        
            q1.pop();
            q2.pop();
        }
        
        if(!q1.empty() || !q2.empty()) return false; 
        else return true;           
            
    }

835. Image Overlap

Two images A and B are given, represented as binary, square matrices of the same size.  (A binary matrix has only 0s and 1s as values.)

We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image.  After, the overlap of this translation is the number of positions that have a 1 in both images.

(Note also that a translation does not include any kind of rotation.)

What is the largest possible overlap?

Example 1:

Input: A = [[1,1,0],
            [0,1,0],
            [0,1,0]]
       B = [[0,0,0],
            [0,1,1],
            [0,0,1]]
Output: 3
Explanation: We slide A to right by 1 unit and down by 1 unit.

Notes: 

1. 1 <= A.length = A[0].length = B.length = B[0].length <= 30
2. 0 <= A[i][j], B[i][j] <= 1

class Solution {
public:
    int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
        int res = 0, n = A.size();
        vector<vector<int>> listA, listB;
        unordered_map<string, int> diffCnt;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (A[i][j] == 1) listA.push_back({i, j});
                if (B[i][j] == 1) listB.push_back({i, j});
            }
        }
        for (auto a : listA) {
            for (auto b : listB) {
                ++diffCnt[to_string(a[0] - b[0]) + "-" + to_string(a[1] - b[1])];
            }
        }
        for (auto diff : diffCnt) {
            res = max(res, diff.second);
        }
        return res;
    }
};

Find And Replace in String

To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y.  The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y.  If not, we do nothing.

For example, if we have S = "abcd" and we have some replacement operation i = 2, x = "cd", y = "ffff", then because "cd" starts at position 2 in the original string S, we will replace it with "ffff".

Using another example on S = "abcd", if we have both the replacement operation i = 0, x = "ab", y = "eee", as well as another replacement operation i = 2, x = "ec", y = "ffff", this second operation does nothing because in the original string S[2] = 'c', which doesn't match x[0] = 'e'.

All these operations occur simultaneously.  It's guaranteed that there won't be any overlap in replacement: for example, S = "abc", indexes = [0, 1], sources = ["ab","bc"] is not a valid test case.

Example 1:

Input: S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
Output: "eeebffff"
Explanation: "a" starts at index 0 in S, so it's replaced by "eee".
"cd" starts at index 2 in S, so it's replaced by "ffff".

Example 2:

Input: S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation: "ab" starts at index 0 in S, so it's replaced by "eee". 
"ec" doesn't starts at index 2 in the original S, so we do nothing.

Notes:

1. 0 <= indexes.length = sources.length = targets.length <= 100
2. 0 < indexes[i] < S.length <= 1000
3. All characters in given inputs are lowercase letters.

===== If indexes are sorted ====

class Solution {

public:

    string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {

        string ans;

        int prev = 0;

        

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

            string pattern = S.substr(indexes[i], sources[i].size());

            if (pattern != sources[i]) {

                continue;

            }

            if (indexes[i] - prev > 0) {

                ans += S.substr(prev, indexes[i] - prev);

            }

            ans += targets[i];

            prev = indexes[i] + sources[i].size();

        }

        if (prev < S.size()) {

            ans += S.substr(prev);

        }

        return ans;

    }

};

==============

string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
        string res = "";
        unordered_map<int, int> m;
        for (int i = 0; i < indexes.size(); ++i) {
            if (S.substr(indexes[i], sources[i].size()) == sources[i]) {
                m[indexes[i]] = i;
            }        
        }
        for (int i = 0; i < S.size();) {
            if (m.count(i)) {
                res += targets[m[i]];
                i += sources[m[i]].size();
            } else {
                res.push_back(S[i]);
                ++i;
            }
        }
        return res;
    }

========

743. Network Delay Time

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

Note:

1. N will be in the range [1, 100].
2. K will be in the range [1, N].
3. The length of times will be in the range [1, 6000].
4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

struct comp {

    bool operator()(pair<int, int>& a, pair<int, int>& b) {

        return a.second > b.second;

    }

};

class Solution {

public:

    int networkDelayTime(vector<vector<int>>& times, int N, int K) {

        unordered_map<int, set<pair<int, int>>> graph;

        generate(graph, N, times);

        return bfs(graph, K);

    }

    

    void generate(unordered_map<int, set<pair<int, int>>>& graph,

                 int N, vector<vector<int>>& times) {

        for (auto edge : times) {

            graph[edge[0]].insert({edge[1], edge[2]});

        }

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

            if (!graph.count(i)) {

                graph[i] = {};

            }

        }

    }

    

    int bfs(unordered_map<int, set<pair<int, int>>>& graph,

           int K) {

        if (!graph.count(K)) {

            return -1;

        }

        

        int node_count = 1, ans = 0, total = 0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, comp> q;

        q.push({K,0});

        unordered_map<int,int> dist;

        dist[K] = 0;

        while (!q.empty()) {

            pair<int, int> node = q.top(); q.pop();

            for (auto neighbor: graph[node.first]) {

                if (!dist.count(neighbor.first) ||

                    dist[neighbor.first] > node.second + neighbor.second) {

                    q.push({neighbor.first, node.second + neighbor.second});

                    dist[neighbor.first] = node.second + neighbor.second;

                }

            }

        }

        if (dist.size() != graph.size()) {

            return -1;

        }

        for (auto entry : dist) {

            ans = max(ans, entry.second);

        }

        return ans;

    }

};

=========== Simple queue works too. May be redundant paths are not there.====

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        int res = 0;
        unordered_map<int, vector<pair<int, int>>> edges;
        vector<int> dist(N + 1, INT_MAX);
        queue<int> q{{K}};
        dist[K] = 0;
        for (auto e : times) edges[e[0]].push_back({e[1], e[2]});
        while (!q.empty()) {
            int u = q.front(); q.pop();
            unordered_set<int> visited;
            for (auto e : edges[u]) {
                int v = e.first, w = e.second;
                if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    if (visited.count(v)) continue;
                    visited.insert(v);
                    q.push(v);
                }
            }
        }
        for (int i = 1; i <= N; ++i) {
            res = max(res, dist[i]);
        }
        return res == INT_MAX ? -1 : res;
    }
};

====================

C++ / Bellman-Ford

Time complexity: O(ne)

Space complexity: O(n)







1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17



// Author: Huahua

// Runtime: 92 ms

class Solution {

public:

    int networkDelayTime(vector<vector<int>>& times, int N, int K) {

        constexpr int MAX_TIME = 101 * 100;

        vector<int> dist(N, MAX_TIME);

        dist[K - 1] = 0;

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

            for (const auto& time : times) {

                int u = time[0] - 1, v = time[1] - 1, w = time[2];

                dist[v] = min(dist[v], dist[u] + w);

            }

        int max_dist = *max_element(dist.begin(), dist.end());

        return max_dist == MAX_TIME ? -1 : max_dist;

    }

};