dfs – My Programming Notes

Tag Archives: dfs

C# || Reconstruct Itinerary – How To Reconstruct Itinerary In Order Using C#

January 01, 2024 admin No comments

The following is a module with functions which demonstrates how to reconstruct itinerary in order using C#.

1. Find Itinerary – Problem Statement

You are given a list of airline tickets where tickets[i] = [from_i, to_i] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Example 1:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"]

Example 2:

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Output: ["JFK","ATL","JFK","SFO","ATL","SFO"] Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

2. Find Itinerary – Solution

The following is a solution which demonstrates how to reconstruct itinerary in order.





		
		
			2. Find Itinerary - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to reconstruct itinerary in order
// ============================================================================
public class Solution {
    public IList<string> FindItinerary(IList<IList<string>> tickets) {
        var map = new Dictionary<string, List<string>>();

        for (int index = 0; index < tickets.Count; ++index) {
            List<string> ticket = tickets[index].ToList();
            string from = ticket[0];
            string to = ticket[1];
            if (!map.ContainsKey(from)) {
                map[from] = new List<string>();
            }
            map[from].Add(to);
        }

        foreach (List<string> list in map.Values) {
            list.Sort();
        }

        var result = new List<string>();
        string start = "JFK";
        result.Add(start);
        DFS(map, start, result, tickets.Count);
        return result;
    }

    private bool DFS(Dictionary<string, List<string>> map, string cur, List<string> result, int totalTicket) {
        if (result.Count == totalTicket + 1) {
            return true;
        }

        if (!map.ContainsKey(cur)) {
            return false;
        }

        List<string> nextList = map[cur];

        for (int index = 0; index < nextList.Count; ++index) {
            string next = nextList[index];
            if (next == null) {
                continue;
            }

            nextList[index] = null;
            result.Add(next);
            if (DFS(map, next, result, totalTicket)) {
                return true;
            }
            // back track
            result.RemoveAt(result.Count - 1);
            nextList[index] = next;
        }

        return false;
    }
}// http://programmingnotes.org/
			
				
					
				
					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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to reconstruct itinerary in order
// ============================================================================
public class Solution {
    public IList<string> FindItinerary(IList<IList<string>> tickets) {
        var map = new Dictionary<string, List<string>>();
 
        for (int index = 0; index < tickets.Count; ++index) {
            List<string> ticket = tickets[index].ToList();
            string from = ticket[0];
            string to = ticket[1];
            if (!map.ContainsKey(from)) {
                map[from] = new List<string>();
            }
            map[from].Add(to);
        }
 
        foreach (List<string> list in map.Values) {
            list.Sort();
        }
 
        var result = new List<string>();
        string start = "JFK";
        result.Add(start);
        DFS(map, start, result, tickets.Count);
        return result;
    }
 
    private bool DFS(Dictionary<string, List<string>> map, string cur, List<string> result, int totalTicket) {
        if (result.Count == totalTicket + 1) {
            return true;
        }
 
        if (!map.ContainsKey(cur)) {
            return false;
        }
 
        List<string> nextList = map[cur];
 
        for (int index = 0; index < nextList.Count; ++index) {
            string next = nextList[index];
            if (next == null) {
                continue;
            }
 
            nextList[index] = null;
            result.Add(next);
            if (DFS(map, next, result, totalTicket)) {
                return true;
            }
            // back track
            result.RemoveAt(result.Count - 1);
            nextList[index] = next;
        }
 
        return false;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

["JFK","MUC","LHR","SFO","SJC"] ["JFK","ATL","JFK","SFO","ATL","SFO"]

C# || Two Sum IV – How To Get Two Numbers In Binary Search Tree Equal To Target Value Using C#

October 09, 2022 admin No comments

The following is a module with functions which demonstrates how to get two numbers in a binary search tree equal to target value using C#.

1. Find Target – Problem Statement

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9 Output: true

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28 Output: false

2. Find Target – Solution

The following are two solutions which demonstrates how to get two numbers in a binary search tree equal to target value.

Both solutions use a set to keep track of the items already seen.

Each time a new node is encountered, we subtract the target value from the current node value. If the difference amount from subtracting the two numbers exists in the set, a 2 sum combination exists in the tree

1. Recursive

The following solution uses Depth First Search when looking for the target value.





		
		
			2. Find Target - Solution - Recursive
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 9, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        return Traverse(root, k, new HashSet<int>());
    }

    private bool Traverse(TreeNode node, int k, HashSet<int> seen) {
        if (node == null) {
            return false;
        }
        // Get remaining value
        var remaining = k - node.val;

        // Check if remaining value has been seen
        if (seen.Contains(remaining)) {
            return true;
        }
        // Add current node value to items seen
        seen.Add(node.val);

        // Keep traversing left and right looking for 2 sum
        return Traverse(node.left, k, seen) || Traverse(node.right, k, seen);
    }
}// http://programmingnotes.org/
			
				
					
				
					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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 9, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        return Traverse(root, k, new HashSet<int>());
    }
 
    private bool Traverse(TreeNode node, int k, HashSet<int> seen) {
        if (node == null) {
            return false;
        }
        // Get remaining value
        var remaining = k - node.val;
 
        // Check if remaining value has been seen
        if (seen.Contains(remaining)) {
            return true;
        }
        // Add current node value to items seen
        seen.Add(node.val);
 
        // Keep traversing left and right looking for 2 sum
        return Traverse(node.left, k, seen) || Traverse(node.right, k, seen);
    }
}// http://programmingnotes.org/

2. Iterative

The following solution uses Breadth First Search when looking for the target value.





		
		
			2. Find Target - Solution - Iterative
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 9, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        // Declare stack
        var stack = new Stack<TreeNode>();

        // Keep track of values seen
        var seen = new HashSet<int>();

        // Add root to stack
        stack.Push(root);

        // Loop through items on the stack
        while (stack.Count > 0) {
            // Get current node
            var node = stack.Pop();

            // Get remaining value
            var remaining = k - node.val;

            // Check if remaining value has been seen
            if (seen.Contains(remaining)) {
                return true;
            } else {
                // Keep traversing left and right looking for 2 sum
                if (node.left != null) {
                    stack.Push(node.left);
                }
                if (node.right != null) {
                    stack.Push(node.right);
                }
            }
            // Add current node value to items seen
            seen.Add(node.val);
        }
        return false;
    }
}// http://programmingnotes.org/
			
				
					
				
					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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 9, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        // Declare stack
        var stack = new Stack<TreeNode>();
 
        // Keep track of values seen
        var seen = new HashSet<int>();
 
        // Add root to stack
        stack.Push(root);
 
        // Loop through items on the stack
        while (stack.Count > 0) {
            // Get current node
            var node = stack.Pop();
 
            // Get remaining value
            var remaining = k - node.val;
 
            // Check if remaining value has been seen
            if (seen.Contains(remaining)) {
                return true;
            } else {
                // Keep traversing left and right looking for 2 sum
                if (node.left != null) {
                    stack.Push(node.left);
                }
                if (node.right != null) {
                    stack.Push(node.right);
                }
            }
            // Add current node value to items seen
            seen.Add(node.val);
        }
        return false;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

true false

C# || Word Search – How To Search A Grid Matrix For A Target Word Using C#

October 11, 2021 admin No comments

The following is a module with functions which demonstrates how to search a grid matrix for a target word using C#.

1. Word Search – Problem Statement

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false

2. Word Search – Solution

The following is a solution which demonstrates how to search a grid matrix for a target word. This solution uses Depth First Search.

Depth First Search (DFS) is an algorithm for searching tree or graph data structures. It starts at the root node and explores as far as possible along each branch before backtracking.

In this problem we start at the root node and search all the possibilities at each array index until a match is found. We create a ‘visited’ array to keep track of the indexes already seen.





		
		
			2. Word Search - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 11, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Determines if a word can be constructed from letters in a grid
// ============================================================================
public class Solution {
    public bool Exist(char[][] board, string word) {

        // Create a 2D bool 'visited' node matrix to keep track of the
        // items we've already seen
        var rowsVisited = new bool[board.Length][];
        for (int rowIndex = 0; rowIndex < board.Length; ++rowIndex) {
            rowsVisited[rowIndex] = new bool[board[rowIndex].Length];
        }

        // Start at the root node and explore as far as possible along each branch
        for (int rowIndex = 0; rowIndex < board.Length; ++rowIndex) {
            for (int colIndex = 0; colIndex < board[rowIndex].Length; ++colIndex) {
                if (DFS(board, rowIndex, colIndex, 0, word, rowsVisited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private bool DFS(char[][] board, int row, int col, int searchIndex, string word, bool[][] rowsVisited) {
        // This is the success case
        if (searchIndex >= word.Length) {
            return true;            
        }
        // Make sure the search parameters are in bounds
        if (row < 0 || row >= board.Length || col < 0 || col >= board[row].Length) {
            return false;            
        }       
        if (rowsVisited[row][col]) {
            return false;            
        } 
        if (board[row][col] != word[searchIndex]) {
            return false;            
        }        
        
        // Mark that this row has been visited
        rowsVisited[row][col] = true;
        
        var searchResult = 
            // Search left
            DFS(board, row, col - 1, searchIndex + 1, word, rowsVisited) ||
            
            // Search right
            DFS(board, row, col + 1, searchIndex + 1, word, rowsVisited) ||
            
            // Search top
            DFS(board, row - 1, col, searchIndex + 1, word, rowsVisited) ||
            
            // Search bottom
            DFS(board, row + 1, col, searchIndex + 1, word, rowsVisited);
        
        // Unmark that this row has been visited
        rowsVisited[row][col] = false;
        
        return searchResult;
    }
}// http://programmingnotes.org/
			
				
					
				
					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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 11, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Determines if a word can be constructed from letters in a grid
// ============================================================================
public class Solution {
    public bool Exist(char[][] board, string word) {
 
        // Create a 2D bool 'visited' node matrix to keep track of the
        // items we've already seen
        var rowsVisited = new bool[board.Length][];
        for (int rowIndex = 0; rowIndex < board.Length; ++rowIndex) {
            rowsVisited[rowIndex] = new bool[board[rowIndex].Length];
        }
 
        // Start at the root node and explore as far as possible along each branch
        for (int rowIndex = 0; rowIndex < board.Length; ++rowIndex) {
            for (int colIndex = 0; colIndex < board[rowIndex].Length; ++colIndex) {
                if (DFS(board, rowIndex, colIndex, 0, word, rowsVisited)) {
                    return true;
                }
            }
        }
        return false;
    }
 
    private bool DFS(char[][] board, int row, int col, int searchIndex, string word, bool[][] rowsVisited) {
        // This is the success case
        if (searchIndex >= word.Length) {
            return true;            
        }
        // Make sure the search parameters are in bounds
        if (row < 0 || row >= board.Length || col < 0 || col >= board[row].Length) {
            return false;            
        }       
        if (rowsVisited[row][col]) {
            return false;            
        } 
        if (board[row][col] != word[searchIndex]) {
            return false;            
        }        
        
        // Mark that this row has been visited
        rowsVisited[row][col] = true;
        
        var searchResult = 
            // Search left
            DFS(board, row, col - 1, searchIndex + 1, word, rowsVisited) ||
            
            // Search right
            DFS(board, row, col + 1, searchIndex + 1, word, rowsVisited) ||
            
            // Search top
            DFS(board, row - 1, col, searchIndex + 1, word, rowsVisited) ||
            
            // Search bottom
            DFS(board, row + 1, col, searchIndex + 1, word, rowsVisited);
        
        // Unmark that this row has been visited
        rowsVisited[row][col] = false;
        
        return searchResult;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

true true false

Tag Archives: dfs

C# || Reconstruct Itinerary – How To Reconstruct Itinerary In Order Using C#

C# || Two Sum IV – How To Get Two Numbers In Binary Search Tree Equal To Target Value Using C#

C# || Word Search – How To Search A Grid Matrix For A Target Word Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories