[Leetcode] DFS & BFS

Posted on | In , |

301. Remove Invalid Parentheses [hard]

Leetcode: https://leetcode.com/problems/remove-invalid-parentheses/description/
Video: https://www.youtube.com/watch?v=2k_rS_u6EBk

[Solution]

  1. Check whether a input string is valid

    1
    2
    count(')') <= count('('), i < n - 1
    count('(') == count(')'), i = n - 1

  2. Compute min number of ‘(‘ and ‘)’ to remove unbalanced ‘)’ + unbalanced ‘(‘

  3. Try all possible ways to remove r‘)’s and l‘(‘s. Remove ‘)’ first to make prefix valid. (have to remove ‘)’ first to make sure prefix is )
    To avoid duplications: only remove the first parentheses if there are consecutive ones
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
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<String>();
        
        // Calculate how many minimum ( and ) need to be removed
        int l = 0;
        int r = 0;
        
        for (int i = 0; i < s.length(); i ++) {
            if (s.charAt(i) == '(') {
                l++;
            }
            if (s.charAt(i) == ')') {
                if (l == 0) r++;
                else l--;
            }
        }
        dfs(r, l, 0, s, res);
        return res;
    }
    
    private boolean isValid(String s) {
        // Use a count to check if parenthesis is valid
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                count++;
            } 
            if (s.charAt(i) == ')') {
                count--;
            }
            if (count < 0) { // ) comes before than (
                return false;
            }
        }
        return count == 0;
    }
    
    // l, r: number of left and right parenthesis to be removed, start: start
    private void dfs(int r, int l, int start, String s, List<String> res) {
        // base condition
        if (r == 0 && l == 0) {
            if (isValid(s)) {
                res.add(s);
            }
        }
        
        for (int i = start; i < s.length(); i++) {
            // Only count first parenthesis if they appear in a consecutive sequence
            if (i != start && s.charAt(i) == s.charAt(i - 1)) continue;
            
            if (s.charAt(i) == '(' || s.charAt(i) == ')') {
                StringBuilder str = new StringBuilder(s);
                str.deleteCharAt(i);
                if (r > 0) dfs(r - 1, l, i, str.toString(), res);
                else if (l > 0) dfs(r, l - 1, i, str.toString(), res);
            }
        }
    }
}
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
class Solution:
    def __init__(self):
        self.res = set()
        
    def removeInvalidParentheses(self, s: str) -> List[str]:
        left = right = 0
        
        for ch in s:
            if ch == '(':
                left += 1
            elif ch == ')':
                if left == 0:
                    right += 1
                else:
                    left -= 1
        def dfs(num_left, num_right, remain_left, remain_right, index, row):
            if index == len(s):
                if num_left == num_right and remain_left == remain_right == 0:
                    self.res.add(row)
                    return
            else:
                if s[index] == '(':
                    if remain_left > 0: # remove (
                        dfs(num_left, num_right, remain_left - 1, remain_right, index + 1, row)
                    dfs(num_left + 1, num_right, remain_left, remain_right, index + 1, row + "(") # keep ( 
                elif s[index] == ')':
                    if remain_right > 0:
                        dfs(num_left, num_right, remain_left, remain_right - 1, index + 1, row) # remove )
                    if num_right < num_left:
                        dfs(num_left, num_right + 1, remain_left, remain_right, index + 1, row + ')') # keep )
                else: # keep other characters
                    dfs(num_left, num_right, remain_left, remain_right, index + 1, row + s[index])
        dfs(0, 0, left, right, 0, "")
        return list(self.res)

872. Leaf-Similar Trees

Leetcode: https://leetcode.com/problems/leaf-similar-trees/description/

[Solution]

  1. Use two stacks to traverse two trees
  2. If node is a leaf, return and compare it
  3. Compare the number of leaves of each trees
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
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        Stack s1 = new Stack();
        Stack s2 = new Stack();
        s1.push(root1);
        s2.push(root2);
        while (!s1.empty() && !s2.empty()) { // traverse all the nodes
            if (dfs(s1).val != dfs(s2).val) return false; // compare all the leaf nodes value
            // continue comparing remaining leaf nodes
        }
        return s1.empty() && s2.empty(); // check if the number of leaves are the same
    }
    
    private TreeNode dfs(Stack s) {
        while (true) { 
            TreeNode cur = (TreeNode)s.pop();
            
            if (cur.left != null) s.push(cur.left);
            if (cur.right != null) s.push(cur.right);
            
            // leaf
            if (cur.left == null && cur.right == null) return cur; // return leaf
        }
    }
}

DFS without tree

394. Decode String

Leetcode: https://leetcode.com/problems/decode-string/

[Solution]
Use a stack to store string and num pairs [[“”, num]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def decodeString(self, s: 'str') -> 'str':
        stack = []
        stack.append(["", 1])
        repeat = ""
        
        for ch in s:
            if ch.isdigit():
                repeat += ch
            elif ch == '[':
                stack.append(["", int(repeat)])
                repeat = ""
            elif ch == ']':
                cur, k = stack.pop()
                stack[-1][0] += cur * k
            else:
                stack[-1][0] += ch
        return stack[0][0]

127. Word Ladder

Leetcode: https://leetcode.com/problems/word-ladder/

[Solution]

  • Construct a dictionary like below

    1
    {"*ot": ["hot", "lot"], "h*t": ["hot"],...}

  • Have a step tracking queue like below

    1
    [("hot", 1),...]

  • Have a visited set to remember visited words

Set() is much faster than list

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
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
    D = {}
    visited = set()
    queue = deque([(beginWord, 1)])
    for word in wordList:
        perms = self.perms(word)
        for perm in perms:
            if perm not in D:
                D[perm] = [word]
            else:
                D[perm].append(word)
                
    while queue:
        cur, step = queue.popleft()
        if cur == endWord:
            return step
        for perm in self.perms(cur):
            neibs = D.get(perm, [])
            for neib in neibs:
                if neib not in visited:
                    queue.append((neib, step + 1))
                    visited.add(neib)
    return 0
    
    def perms(self, word):
        return [word[:i] + '*' + word[i+1:] for i in range(len(word))]

128. Longest Consecutive Sequence

Leetcode: https://leetcode.com/problems/longest-consecutive-sequence/
[Solution]

  • Have a visited set to remember visited nodes
  • Use a stack [[num, len]] to do DFS
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
def longestConsecutive(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    visited = set()
    if len(nums) == 0:
        return 0
    maxL = 1
    for num in nums:
        if num in visited:
            continue
        stack = [[num, 1]]
        while stack:
            cur, l = stack.pop()
            # print(cur, l)
            maxL = max(maxL, l)

            neibs = [cur - 1, cur + 1]
            for neib in neibs:
                if neib in nums and neib not in visited:
                    if stack:
                        stack[0][1] += 1
                    stack.append([neib, l + 1])

            visited.add(cur)
    return maxL

Leetcode: https://leetcode.com/problems/word-search/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def exist(self, board: List[List[str]], word: str) -> bool:
    def search(i, j, index):
        # print(board[cur[0]][cur[1]], index, visited)
        if i < 0 or i == len(board) or j < 0 or j == len(board[0]) or index == len(word) or board[i][j] != word[index]:
            return False
        if index == len(word) - 1 and board[i][j] == word[index]:
            return True
        
        temp = board[i][j]
        board[i][j] = "#"
        
        if search(i - 1, j, index + 1) or search(i + 1, j, index + 1) or search(i, j + 1, index + 1) or search(i, j - 1, index + 1):
            return True
        
        board[i][j] = temp
        return False
                
    for i in range(len(board)):
        for j in range(len(board[0])):
            if search(i, j, 0):
                return True
    return False

332. Reconstruct Itinerary

Leetcode: https://leetcode.com/problems/reconstruct-itinerary/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
    graph = {}
    for ticket in tickets:
        if ticket[0] in graph:
            graph[ticket[0]].append(ticket[1])
        else:
            graph[ticket[0]] = [ticket[1]]
        if ticket[1] not in graph:
            graph[ticket[1]] = []
    for t in graph:
        graph[t].sort(reverse = True)
    stack = ['JFK']
    res = []
    while stack:
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop())
        res.append(stack.pop())
    return res[::-1]

399. Evaluate Division

Leetcode: https://leetcode.com/problems/evaluate-division/

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
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
    graph = {} # {a: {b: 2}, b: {c: 3, a: 0.5}, c: { b: 1/3}}
    for i in range(len(equations)): 
        if equations[i][0] in graph:
            children = graph[equations[i][0]]
            children[equations[i][1]] = values[i]
        else:
            graph[equations[i][0]] = {equations[i][1]: values[i]}
        if equations[i][1] in graph:
            children = graph[equations[i][1]]
            children[equations[i][0]] = 1 / values[i]
        else:
            graph[equations[i][1]] = {equations[i][0]: 1 / values[i]}
    res = []
    
    def calculate(x, y):
        visited = set()
        stack = [(x, 1.0)]
        while stack:
            cur, times = stack.pop()
            visited.add(cur)
            if cur == y:
                return times
            neibs = graph[cur]
            for nb in neibs:
                if nb not in visited:
                    stack.append((nb, times * neibs[nb]))
        return -1.0
        
    for query in queries:
        # x / y
        if query[0] not in graph or query[1] not in graph:
            res.append(-1.0)
        else:
            res.append(calculate(query[0], query[1]))
    return res

329. Longest Increasing Path in a Matrix

Leetcode: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

Solution 1: Naive DFS (TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
    if not matrix or not matrix[0]:
        return 0
    self.res = 0
    def dfs(path, visited, prev, i, j):
        if (i, j) in visited or i < 0 or j < 0 or i == len(matrix) or j == len(matrix[0]) or (prev and matrix[i][j] <= prev):
            return
        if matrix[i][j] == prev:
            return
        prev = matrix[i][j]
        path.append(prev)
        self.res = max(self.res, len(path))
        visited.add((i, j))
        dfs(path, visited,prev, i + 1, j)
        dfs(path, visited,prev, i - 1, j)
        dfs(path, visited,prev, i, j + 1)
        dfs(path, visited,prev, i, j - 1)
        path.pop()
        visited.remove((i, j))
        
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            dfs([], set(), None, i, j)
    return self.res

Optimize: Memoization

Note:

  • Use a cache matrix to remember if we’ve already calculated the current cell
  • If so, directly return that from cache
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
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
    if not matrix or not matrix[0]:
        return 0
    cache = [[0 for j in range(len(matrix[0]))] for i in range(len(matrix))]
    self.res = 0
    def dfs(visited, prev, i, j, maximum, cache):
        if (i, j) in visited or i < 0 or j < 0 or i == len(matrix) or j == len(matrix[0]) or (prev and matrix[i][j] <= prev):
            return 0
        if matrix[i][j] == prev:
            return 1
        if cache[i][j] != 0:
            return cache[i][j]
        prev = matrix[i][j]
        maximum += 1
        visited.add((i, j))
        res = max([dfs(visited, prev, i + 1, j, maximum, cache),
                dfs(visited,prev, i - 1, j, maximum, cache),
                dfs(visited,prev, i, j + 1, maximum, cache),
                dfs(visited,prev, i, j - 1, maximum, cache)]) + 1
        cache[i][j] = max(cache[i][j], res)
        visited.remove((i, j))
        maximum -= 1
        return cache[i][j]
    res = 0
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            res = max(res, dfs(set(), None, i, j, 0, cache))
    return res