Fork me on GitHub
image frame

Yangyang

Think. Learn. Create
Try to update hard.

Leetcode Study Day 47

Leetcode

Implement Trie (Prefix Tree)

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True
 

Constraints:

1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 104 calls in total will be made to insert, search, and startsWith.

My solution

My solution is easy to understand but cost a lot of time to process.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Trie {
public:
    Trie() {
       
    }
    
    void insert(string word) {
         wordSet.insert(word);
    }
    
    bool search(string word) {
        if (wordSet.find(word) != wordSet.end())
            return true;
        else return false;
    }
    
    bool startsWith(string prefix) {
        int n = prefix.size();
        for(string word: wordSet){
            for(int i = 0; i < n; i++){
                if(prefix[i] != word[i])
                    break;
                if(prefix[i] == word[i] && i == n - 1)
                    return true;    
            }
        }
        return false;
    }

private:
    unordered_set <string> wordSet;

};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

Prefix Tree

I got the idea of using prefix tree from this post in Leetcode.

I am going to explain his code with comment:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class TrieNode {
public:
    // create an array with 26 TrieNode pointers
    TrieNode* children[26];
    bool isWordCompleted;

    TrieNode() {
        memset(children, 0, sizeof(children));
        isWordCompleted = false;
    }
};

class Trie {
public:
    TrieNode *root;
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* newRoot = root;
        for (char ch : word) {
            // get the index of the alphabet
            int alphabetIndex = ch - 'a';
            // if the pointer is NULL, create a new TrieNode
            if (newRoot -> children[alphabetIndex] == NULL) {
                newRoot -> children[alphabetIndex] = new TrieNode();
            } 
            // move the pointer to the next TrieNode
            newRoot = newRoot -> children[alphabetIndex];
        }
        // mark the word as completed
        newRoot -> isWordCompleted = true;
    }
    
    bool search(string word) {
        TrieNode* newRoot = root;
        for (char ch : word) {
            int alphabetIndex = ch - 'a';
            // if the pointer is NULL, means the character is not in the tree
            if (newRoot -> children[alphabetIndex] == NULL) {
                return false;
            } 
            newRoot = newRoot -> children[alphabetIndex];
        }
        // if the word is completed, return true
        if (newRoot -> isWordCompleted == true) {
            return true;
        }
        return false;
    }
    
    bool startsWith(string prefix) {
        TrieNode* newRoot = root;
        for (char ch : prefix) {
            int alphabetIndex = ch - 'a';
            if (newRoot -> children[alphabetIndex] == NULL) {
                return false;
            } 
            newRoot = newRoot -> children[alphabetIndex];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

Design Add and Search Words Data Structure

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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 <= 25
word in addWord consists of lowercase English letters.
word in search consist of '.' or lowercase English letters.
There will be at most 2 dots in word for search queries.
At most 104 calls will be made to addWord and search.

Solution

Based on the idea of previous problem, we can use prefix tree to solve this problem. The only difference is that we need to consider the ‘.’ in the word. We can use recursive method to search the word in the tree. If we meet ‘.’, we need to search all the children of the current node. If the node we find is not correct, we need to move to the next node. If we run out of all 26 alphabet, we return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class TrieNode{
    public:
    TrieNode* children[26];
    bool isCompleted;
    TrieNode(){
        memset(children, 0, sizeof(children));
        isCompleted = false;
    }
};

class WordDictionary {   
public:
    TrieNode *root ;
    WordDictionary() {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        TrieNode * newroot = root;
        for(char character: word){
            int alphabetIndex = character - 'a';
            if(newroot->children[alphabetIndex] == NULL)
                newroot->children[alphabetIndex] = new TrieNode();
            newroot = newroot->children[alphabetIndex];
        }
        newroot -> isCompleted = true;
    }
    
    bool search(string word) {
        return searchRecursive(word, 0, root);
    }
private:
    bool searchRecursive(const string & word, int index, TrieNode* node){
        if (index == word.size()){
            return node->isCompleted;
        }
        char ch = word[index];
        if(ch != '.'){
            int alphabetIndex = ch - 'a';
            if(node->children[alphabetIndex] == NULL)
                return false;
            return searchRecursive(word, index + 1, node->children[alphabetIndex]);       
        }
        if(ch == '.'){
            for (int i = 0; i < 26; i++){
                if(node->children[i] != NULL){
                    if (searchRecursive(word, index + 1, node->children[i]))
                        return true;
                }
            }
        }
        return false;
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

Leetcode Study Day 46

Leetcode

Minimum Genetic Mutation

A gene string can be represented by an 8-character long string, with choices from ‘A’, ‘C’, ‘G’, and ‘T’.

Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.

For example, “AACCGGTT” –> “AACCGGTA” is one mutation.
There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.

Given the two gene strings startGene and endGene and the gene bank bank, return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such a mutation, return -1.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1
Example 2:

Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2
 

Constraints:

0 <= bank.length <= 10
startGene.length == endGene.length == bank[i].length == 8
startGene, endGene, and bank[i] consist of only the characters ['A', 'C', 'G', 'T'].

Solution

I asked ChatGPT for get some hints and pseudo codes, in general, his idea is to use BFS to find the shortest path. He stored the bank gene into a set. Then use BFS to store and pop the mutated gene.

Here is his pseudo code:

1
2
3
4
5
6
7
8
9
10
11
12
This problem can be approached as a graph traversal problem, where each gene string represents a node and a mutation is an edge between two nodes. The goal is to find the shortest path from the startGene to the endGene. Here's a step-by-step approach using Breadth-First Search (BFS), which is well-suited for finding the shortest path in unweighted graphs:

Initialize: Create a queue for BFS and a set to keep track of visited nodes. Add the startGene to the queue.

BFS Loop:

While the queue is not empty, remove the first gene from the queue.
Check if this gene is the endGene. If yes, return the number of mutations (depth) required to reach this gene.
Otherwise, iterate over each character in the gene. For each character, try changing it to the other three possible nucleotides ('A', 'C', 'G', 'T').
For each modified gene, check if it is in the bank and not yet visited.
If so, add it to the queue and mark it as visited.
Return -1: If the queue gets empty and the endGene is not found, return -1, indicating no possible mutation path.

Here’s a pseudo-code to illustrate this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
pseudo
function minGeneticMutation(startGene, endGene, bank):
    if endGene not in bank:
        return -1

    bankSet = set(bank)
    visited = set()
    queue = [(startGene, 0)]  # (current gene, mutation steps)

    while queue is not empty:
        currentGene, steps = queue.pop(0)
        
        if currentGene == endGene:
            return steps

        for i in 0 to length(currentGene) - 1:
            for nucleotide in ['A', 'C', 'G', 'T']:
                if nucleotide != currentGene[i]:
                    mutatedGene = currentGene[:i] + nucleotide + currentGene[i+1:]
                    if mutatedGene in bankSet and mutatedGene not in visited:
                        queue.append((mutatedGene, steps + 1))
                        visited.add(mutatedGene)

    return -1

Full code

Here is my code based on the pseudo code above, one thing I learnt is that we can use substr to split the string:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        vector <char> geneChar = {'A','C','G','T'};
        if(find(bank.begin(), bank.end(), endGene) == bank.end())
            return -1;
        set<string> bankSet;
        for (int i = 0; i < bank.size(); i++)
            bankSet.insert(bank[i]);
        set<string> visited;
        queue <pair<string, int>> bankQ;
        bankQ.push({startGene,0});
        while (!bankQ.empty()){
            string current = bankQ.front().first;
            int step = bankQ.front().second;
            bankQ.pop();
            if (current == endGene){
                return step;
            }
            for(int i = 0; i < current.size(); i++){
                for(char singleGene: geneChar){
                    string mutatedGene = current.substr(0, i) + singleGene + current.substr(i + 1, current.size());
                    if (bankSet.find(mutatedGene)!= bankSet.end() && visited.find(mutatedGene) == visited.end()){
                        bankQ.push({mutatedGene, step+1});
                        visited.insert(mutatedGene);
                    }
                }
            }
        }
        return -1;
    }
};

Word Ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:

Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
 

Constraints:

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters.
beginWord != endWord
All the words in wordList are unique.

My solution

The main idea is similar to the previous one, which is to use BFS to find the shortest path. The only difference is that this time we need to find the words with only one word difference between the original one, whereas the previous one is to try to replace each character with the four characters.

Here is my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int difference(string current, string word){
        int diff = 0;
        for (int i = 0; i < current.size(); i++){
            if (current[i] != word[i])
                diff ++;
            if (diff > 1)
                break;
        }
        return diff;
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        if(find(wordList.begin(), wordList.end(), endWord) == wordList.end())
            return 0;
        unordered_set<string> wordSet;
        for (int i = 0; i < wordList.size(); i++)
            wordSet.insert(wordList[i]);
        unordered_set<string> visited;
        queue <pair<string, int>> wordQ;
        wordQ.push({beginWord,1});
        while (!wordQ.empty()){
            string current = wordQ.front().first;
            int step = wordQ.front().second;
            wordQ.pop();
            if (current == endWord){
                return step;
            }
            for (string word: wordSet){
                if (difference(current, word) == 1 && visited.find(word) == visited.end()){
                    wordQ.push({word,step+1});
                    visited.insert(word);
                }
            }
        }
        return 0;
    }
};

Leetcode Study Day 45

Leetcode

Snakes and Ladders

You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)].
This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
The game ends when you reach the square n2.
A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 do not have a snake or ladder.

Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.
Return the least number of moves required to reach the square n2. If it is not possible to reach the square, return -1.

Alt text 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Example 1:


Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation: 
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.
Example 2:

Input: board = [[-1,-1],[-1,3]]
Output: 1
 

Constraints:

n == board.length == board[i].length
2 <= n <= 20
board[i][j] is either -1 or in the range [1, n2].
The squares labeled 1 and n2 do not have any ladders or snakes.

Solution

I found this solution from Leetcode. Here is his explanation:

Intuition

The intuition behind this code is that it uses a breadth-first search (BFS) algorithm to find the minimum number of moves required to reach the last cell of the board from the first cell. BFS is an algorithm that explores all the vertices of a graph or all the nodes of a tree level by level.

Approach

The method starts by creating a vector of pairs called “cells” that stores the row and column of each cell in the board. It also creates a vector of integers called “dist” that stores the minimum number of moves required to reach each cell and initializes it to -1.

It then uses a queue to keep track of the cells to be visited and starts by pushing the first cell (cell 1) into the queue. The method then enters a while loop that continues until the queue is empty. In each iteration of the loop, it takes the front element of the queue, which is the current cell, and pops it from the queue.

For the current cell, the method loops through all the possible next cells which are from curr+1 to min(curr+6,n*n) (because in each move we can move to a dice roll max 6 steps) and checks if the minimum number of moves required to reach that cell has not been assigned yet. If it has not been assigned yet, the method assigns the minimum number of moves required to reach that cell as the minimum number of moves required to reach the current cell plus one. It also pushes the next cell into the queue to be visited in the next iteration.

The method then continues this process until all the cells have been visited, and the minimum number of moves required to reach each cell has been assigned. Finally, the method returns the minimum number of moves required to reach the last cell, which is stored in dist[n*n].

It also handles the case if there is a snake or ladder at the cell, it directly assigns the destination cell number as the cell number.

Complexity

Time complexity:

The time complexity of this code is O(n^2), where n is the size of the board. This is because the method uses a breadth-first search algorithm to traverse through each cell of the board and assigns the distance of each cell from the starting cell. The outer loop iterates n times, and the inner loop iterates n times, so the total number of iterations is n*n.

Note that this is assuming the queue and vector operations have a constant time complexity, which is typical but not guaranteed.

Space complexity:

The space complexity of this code is also O(n^2). This is because the method uses a vector of integers called “dist” to keep track of the minimum number of moves required to reach each cell, and this vector has nn elements. The method also uses a vector of pairs called “cells” to keep track of the row and column of each cell, and this vector also has nn elements. The method also uses a queue to keep track of the cells to be visited, which can have at most n*n elements.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int snakesAndLadders(vector<vector<int>> &board) {
        int n = board.size(), lbl = 1;
        vector<pair<int, int>> cells(n*n+1);
        vector<int> columns(n);
        iota(columns.begin(), columns.end(), 0);
        for (int row = n - 1; row >= 0; row--) {
            for (int column : columns) {
                cells[lbl++] = {row, column};
            }
            reverse(columns.begin(), columns.end());
        }
        vector<int> dist(n*n+1, -1);
        dist[1] = 0;
        queue<int> q;
        q.push(1);
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            for (int next = curr + 1; next <= min(curr+6, n*n); next++) {
                auto [row, column] = cells[next];
                int destination = board[row][column] != -1 ? board[row][column] : next;
                if (dist[destination] == -1) {
                    dist[destination] = dist[curr] + 1;
                    q.push(destination);
                }
            }
        }
        return dist[n*n];
    }
};

Leetcode Study Day 45

Leetcode

Course Schedule II

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]
 

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
All the pairs [ai, bi] are distinct.

Solution

The solution is similar to the previous question, except this time we add a stack to store the courses we want to take. After we find the courses that need to be taken in the end, we push them into the stack. After finding all the courses and make sure there is no cycle, we pop the stack and store the courses in the vector. The order of the courses is the reverse order of the stack. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    bool iscycle(vector<int> adj[], vector<int> &vis, int id, stack<int> &courseStack) {
        if(vis[id] == 1)
            return true;
        if(vis[id] == 0){
            vis[id] = 1;
            for(int edge : adj[id]){
                if(iscycle(adj, vis, edge, courseStack))
                    return true;
            }
            courseStack.push(id);
        }
        vis[id] = 2;
        return false;
    }

    vector<int> findOrder(int n, vector<vector<int>>& pre) {
        vector<int> adj[n];
        for(auto edge : pre)
            adj[edge[1]].push_back(edge[0]);
        
        vector<int> vis(n, 0);
        stack<int> courseStack;
        for(int i = 0; i < n; i++){
            if(vis[i] == 0){
                if(iscycle(adj, vis, i, courseStack))
                    return {}; // Return empty if cycle is detected
            }
        }

        vector<int> order;
        while(!courseStack.empty()){
            order.push_back(courseStack.top());
            courseStack.pop();
        }
        return order;
    }
};

Leetcode Study Day 44

Leetcode

Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.
Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
 

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique.

Solution

I found this solution from Leetcode. Here is his explanation:

We just have to find if our graph contains cycle or not because if graph contains cycle then all tnodes in cycle are interdependent and 1 course cannot be completed because its prerequisite is dependent on other course and it goes on .
We used coloring algorithm to find if there is cycle in graph or not.

Coloring Algorithm

vis[id]=0 is used for node which is not yet visited, vis[id]=1 is used for the node which is visited and currently its child nodes are being visited and vis[id]=2 done when all the child nodes of a node (“id”) are visited and the function returns to parent node of node (“id”). So at that time it is marked as 2 because this node does not require any further traversing.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    bool iscycle(vector<int> adj[],vector<int> &vis,int id){
        // if we find this node again, we can make sure it's a cycle
        if(vis[id]==1)
            return true;
        // if it's a new node
        if(vis[id]==0){
            // we set it as 1
            vis[id]=1;
            // we check all its adjacent nodes
            for(int edge : adj[id]){
                if(iscycle(adj,vis,edge))
                    return true;
            }
        }
        vis[id] = 2;
        return false;
    }
    bool canFinish(int n, vector<vector<int>>& pre) {
        // a vector with n elements, each element is a vector
        vector<int> adj[n];
        for(auto edge : pre)
            // push the pre[2]th number with course pre[1]
            adj[edge[1]].push_back(edge[0]);
        // a vector with n elements, each element is 0
        vector<int> vis(n,0);
        
        for(int i=0;i<n;i++){
            // if we find a cycle, return false
            if(iscycle(adj,vis,i))
                return false;
        }
        return true;
    }
};

Leetcode Study Day 44

Leetcode

Evaluate Division

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
note: x is undefined => -1.0
Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]
Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]
 

Constraints:

1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj consist of lower case English letters and digits.

Solution

For the solution, we use a nested map to record the graph. To be specific, we can imagine string a is a node, it map to string b, where the edge value is a/b, whcih is 1.5, it is the value that b mapped to. So we create a structure to store this nested map: 

1
unordered_map <string, unordered_map<string, double>>

Let me explain the code below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        // create the nested map with input equations
        unordered_map <string, unordered_map<string, double>> graph = createGraph(equations, values);
        // create the result vector
        vector<double> res;
        // for each query, we find the path product
        for (int i = 0; i < queries.size(); i++){
            if (queries[i][0] == queries[i][1] && graph.find(queries[i][0]) != graph.end())
                res.push_back(1.0); //Division of a number by itself
            else if (graph.find(queries[i][0]) == graph.end() || graph.find(queries[i][1]) == graph.end())
                res.push_back(-1.0); // if we cannot find the node in the graph
            else{
                // we find the path product and push it to the result vector
                double result = findPathProduct(graph, queries[i][0], queries[i][1]);
                res.push_back(result);
                }
        }
        return res;
    }

    // Create graph function
    unordered_map <string, unordered_map<string, double>> createGraph(vector<vector<string>>& equations,vector<double>& values){
        unordered_map <string, unordered_map<string, double>> graph;
        
        for (int i = 0; i < equations.size(); i++){
            double value = values[i];
            string A = equations[i][0];
            string B = equations[i][1];
            // store the value in the nested map
            graph[A][B] = value;
            // store the reverse value in the nested map
            graph[B][A] = 1.0 / value;
                
        }
        return graph;
    }

    // Find path product function
    double findPathProduct(unordered_map <string, unordered_map<string, double>>& graph, string& start, string& end){
        // create a set to store the visited node
        set<string> visited;
        return dfs(graph, start, end, 1.0, visited);
    }

    // DFS function
    double dfs(unordered_map<string, unordered_map<string, double>>& graph, const string& current, const string& end, double product, set<string>& visited){
        // if we have visited the node, we return -1.0
        if(visited.find(current)!= visited.end())
            return -1.0;
        // if we find the end node, we return the product
        if (current == end)
            return product;
        // we add the current node to the visited set
        visited.insert(current);
        // for each neighbor of the current node, we find the path product
        for (const auto& pair : graph[current]) {
            const string& neighbor = pair.first;
            double weight = pair.second;
            // we use dfs to find the path product
            double pathProduct = dfs(graph, neighbor, end, product * weight, visited);
            // if we find the path product, we return it
            if (pathProduct != -1.0)
                return pathProduct;
        }
        // if we cannot find the path product, we return -1.0
        visited.erase(current);
        return -1.0;
    }
};

Leetcode Study Day 43

Leetcode

Clone Graph

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Node {
    public int val;
    public List<Node> neighbors;
}
 

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Example 1:


Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
Example 2:


Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
 

Constraints:

The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
Node.val is unique for each node.
There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.

Solution

The solution from Leetcode used DFS to solve this question. Here is the full explanation:

OBSERVATIONS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1. Cloned Graph has all nodes as newnodes and don't have node as reference to given original graph.
2. Graph has no practical edges, i.e no pointers for edges.
         (2,3)            (1,3)<---adj list
		  (1)-------------(2)
		    |              |
			|              |
			|              |
		  (4)-------------(3)
		  (1,3)          (2,4)
If i say '1' is my starting point and how should i jump to '2' for that i have to iterate through this adjacency list.
ALGORITHM TO USE
We need to traverse all node of original graph and as soon as we reach a node, we will make a copy node.
And recur for rest of the graph.
This is a typical recursion type problem implemented on Graph.
For 'Recursion' we use basically 'DFS' or 'BFS'.
I am using DFS

KEY POINTS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
1. We use HashMap to solve it and using DFS.
2. Initially our hash map will be empty and we try to map the old node with the new node or the copy node.
3. We start with any entry point.
4. I am using '1' as my entry point.

Now lets see how its going i am starting with 1 and whenever i visited a new node i coloned it and put in there.
We are using DFS so algorithm is like 'it starts at the root node (select some arbitrary node as root node in the case of a graph) and explores as far as possible along each branch before backtracking.
So the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacentunmarked node and continue this loop until there is no unmarked adjacent node. 
Then backtrack and check for other unmarked nodes and traverse them. Finally, print the nodes in the path.'
So we are using HashMap to put all the visited node or old node there with clone one to.
 _________
| HashMap |
 ----------
|Old|Clone| 
| 1  | 1 |
|  2 | 2 |
|  3 | 3 |                                                     
|  4 | 4 |                                                                                                            
---------

Now i started with 1 so i cloned it and from 1 can go to 2 and 4 so i go 2 and when i visited 2 i cloned 2 and now fro  i have two choices either go to previous one that is 1 or discover 3 i.e new node
so accordingly to dfs i go to 3 and from 3 i can go to 4 i go there and cloned it. Now if we see fro each node we have viisted to a new node but what about 4. So here half part of Dfs is completed,
and now its time for recursive call to go back and now from here we check from current node i can go where and where.
And follow the same rules over there.

BUT BEFORE STARTING ANY CLONING WE HAVE TO CHECK THAT IF WE HAVE CLONED THAT NODE ALREADY THERE OR NOT. IF NOT THAN ONLY WE CLONED IT. 

Thats the only reason we are using hash map so that we don't need to clone again and again.
For every uncloned node we make a clone and iterate over the neighbors of original node using dfs traversal or

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public:
    Node* dfs(Node* cur,unordered_map<Node*,Node*>& mp)
    {
        vector<Node*> neighbour;
        Node* clone=new Node(cur->val);
        mp[cur]=clone;
            for(auto it:cur->neighbors)
            {
                if(mp.find(it)!=mp.end())   //already clone and stored in map
                {
                    neighbour.push_back(mp[it]);    //directly push back the clone node from map to neigh
                }
                else
                    neighbour.push_back(dfs(it,mp));
            }
            clone->neighbors=neighbour;
            return clone;
    }
    
    Node* cloneGraph(Node* node) {
        unordered_map<Node*,Node*> mp;
        if(node==NULL)
            return NULL;
        if(node->neighbors.size()==0)   //if only one node present no neighbors
        {
            Node* clone= new Node(node->val);
            return clone; 
        }
        return dfs(node,mp);
    }
};

Leetcode Study Day 43

Leetcode

Surrounded Regions

Given an m x n matrix board containing ‘X’ and ‘O’, capture all regions that are 4-directionally surrounded by ‘X’.
A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Example 1:


Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.
Example 2:

Input: board = [["X"]]
Output: [["X"]]
 

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is 'X' or 'O'.

Solution

The solution is like the island problem. We use DFS to solve this question.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
public:
    void DFS(vector<vector<char>>& board, int i, int j, int m, int n) {
        if(i<0 or j<0 or i>=m or j>=n or board[i][j] != 'O') return;
        board[i][j] = '#';
        DFS(board, i-1, j, m, n);
        DFS(board, i+1, j, m, n);
        DFS(board, i, j-1, m, n);
        DFS(board, i, j+1, m, n);
    }
    
    void solve(vector<vector<char>>& board) {
      
      //We will use boundary DFS to solve this problem
        
      // Let's analyze when an 'O' cannot be flipped,
      // if it has atleast one 'O' in it's adjacent, AND ultimately this chain of adjacent 'O's is connected to some 'O' which lies on boundary of board
        
      //consider these two cases for clarity :
      /*
        O's won't be flipped          O's will be flipped
        [X O X X X]                   [X X X X X]     
        [X O O O X]                   [X O O O X]
        [X O X X X]                   [X O X X X] 
        [X X X X X]                   [X X X X X]
      
      So we can conclude if a chain of adjacent O's is connected some O on boundary then they cannot be flipped
      
      */
        
      //Steps to Solve :
      //1. Move over the boundary of board, and find O's 
      //2. Every time we find an O, perform DFS from it's position
      //3. In DFS convert all 'O' to '#'      (why?? so that we can differentiate which 'O' can be flipped and which cannot be)   
      //4. After all DFSs have been performed, board contains three elements,#,O and X
      //5. 'O' are left over elements which are not connected to any boundary O, so flip them to 'X'
      //6. '#' are elements which cannot be flipped to 'X', so flip them back to 'O'
      //7. finally, Upvote the solution😊   
        
      
     int m = board.size();
        
      if(m == 0) return;  
        
     int n = board[0].size();
     
     //Moving over firts and last column   
     for(int i=0; i<m; i++) {
         if(board[i][0] == 'O')
             DFS(board, i, 0, m, n);
         if(board[i][n-1] == 'O')
             DFS(board, i, n-1, m, n);
     }
        
        
     //Moving over first and last row   
     for(int j=0; j<n; j++) {
         if(board[0][j] == 'O')
             DFS(board, 0, j, m, n);
         if(board[m-1][j] == 'O')
             DFS(board, m-1, j, m, n);
     }
        
     for(int i=0; i<m; i++)
         for(int j=0; j<n; j++)
         {
             if(board[i][j] == 'O')
                 board[i][j] = 'X';
             if(board[i][j] == '#')
                 board[i][j] = 'O';
         }
    }
};

Leetcode Study Day 42

Leetcode

Number of Islands

Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1
Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3
 

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

Solution

I saw a wonderful solution using DFS to solve this question in python. I convert it into C++ version.

In this code, we frist iterate the grid from the top left corner to the bottom right corner. If we find a ‘1’, we use dfs to find all the adjacent ‘1’ and change them into ‘#’. Then we increase the count by 1. Finally, we return the count.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    void dfs(vector<vector<char>>& grid, int i, int j){
        if (i < 0 || j <0 || i >= grid.size() || j >= grid[0].size() || grid[i][j]!= '1')
            return;
        grid[i][j] = '#';
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }

    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty())
            return 0;
        int count = 0;
        for (int i = 0;i < grid.size(); i ++){
            for (int j = 0; j < grid[0].size(); j++){
                if (grid[i][j] == '1'){
                    dfs(grid, i, j);
                    count ++;
                }
            }
        }
        return count;
    }
};

Leetcode Study Day 42

Leetcode

Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left
subtree
of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Example 1:


Input: root = [2,1,3]
Output: true
Example 2:


Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
 

Constraints:

The number of nodes in the tree is in the range [1, 104].
-231 <= Node.val <= 231 - 1

My solution

My solution is initialise a NodeTree variable called prev. Then we use in-order traverse to traverse the tree. If the previous node value is larger or equal to the current node value, then we return false. Otherwise, we return true.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* prev = nullptr;
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        if (!isValidBST(root -> left)) return false;
        if (prev != nullptr && prev -> val >= root -> val)
            return false;
        prev = root;
        return (isValidBST(root -> right));
    }
};
  • Copyrights © 2020-2024 Yangyang Cui

请我喝杯咖啡吧~

支付宝
微信