Title: Chapter 45: Dynamic Programming (Part 5) – Wildcard Matching, Catalan's Number, Counting BSTs, and Mountain Ranges

Introduction

Welcome to Part 5 of the Dynamic Programming series! In this chapter, we'll tackle challenging problems that involve pattern matching, combinatorics, and counting structures. Topics include:

• Wildcard Matching (explanation and code)

• Catalan's Number (using both recursion with memoization and tabulation)

• Counting Binary Search Trees

• Mountain Ranges problem

Let’s dive into each topic with detailed explanations and code examples.

---

1. Wildcard Matching (Hard)

1.1 Understanding Wildcard Matching

Wildcard Matching is a pattern matching problem where we match a string against a pattern containing special characters:

• * matches any sequence of characters (including an empty sequence).

• ? matches any single character.

1.2 Dynamic Programming Approach

The key to solving this problem is to use dynamic programming to handle overlapping subproblems. We define dp[i][j] as:

• True if the substring s[0...i] matches the pattern p[0...j]

• False otherwise.

1.3 Code for Wildcard Matching

public boolean isMatch(String s, String p) {
    int m = s.length();
    int n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;

    for (int j = 1; j <= n; j++) {
        if (p.charAt(j - 1) == '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }

    return dp[m][n];
}

---

2. Catalan's Number

2.1 Introduction to Catalan Numbers

The Catalan sequence is a series of numbers that appear in various combinatorial counting problems, such as counting unique binary search trees, valid parentheses expressions, and paths in a grid.

2.2 Catalan Numbers (Recursion + Memoization)

Using recursion with memoization, we can avoid redundant computations and efficiently compute Catalan numbers.

Code: Catalan Number (Recursion + Memoization)

public class CatalanNumbers {
    private Map<Integer, Integer> memo = new HashMap<>();

    public int catalan(int n) {
        if (n <= 1) return 1;
        if (memo.containsKey(n)) return memo.get(n);

        int result = 0;
        for (int i = 0; i < n; i++) {
            result += catalan(i) * catalan(n - 1 - i);
        }

        memo.put(n, result);
        return result;
    }
}

---

2.3 Catalan Numbers (Tabulation)

Tabulation is an alternative method that builds the solution iteratively and stores the results in an array for direct access.

Code: Catalan Number (Tabulation)

public int catalanTabulation(int n) {
    int[] catalan = new int[n + 1];
    catalan[0] = 1;
    catalan[1] = 1;

    for (int i = 2; i <= n; i++) {
        catalan[i] = 0;
        for (int j = 0; j < i; j++) {
            catalan[i] += catalan[j] * catalan[i - j - 1];
        }
    }
    return catalan[n];
}

---

3. Count BSTs

3.1 Problem Explanation

Counting the number of unique Binary Search Trees (BSTs) that can be formed using n nodes is another application of Catalan numbers.

3.2 Code for Counting BSTs

Using the Catalan number function, we can directly compute the number of unique BSTs for n nodes.

public int countBSTs(int n) {
    return catalanTabulation(n); // Reuse the catalanTabulation function from above
}

---

4. Mountain Ranges

4.1 Introduction to Mountain Ranges Problem

The Mountain Ranges problem is a combinatorial problem where we aim to count valid mountain ranges (or paths) of a certain length. Each valid path must start and end at the same level without dipping below the starting point.

4.2 Solution with Dynamic Programming

This problem can also be solved using the Catalan numbers, as it represents valid sequences of peaks and valleys.

4.3 Code for Counting Mountain Ranges

Using the Catalan number for n, we can determine the number of valid mountain ranges of height n.

public int countMountainRanges(int n) {
    return catalanTabulation(n); // Reuse the catalanTabulation function from above
}

---

Conclusion

In this chapter, we explored the applications of Catalan numbers in various combinatorial problems and how to use dynamic programming for pattern matching with wildcards. These are fundamental problems that test our understanding of recursive and iterative solutions.

---

Additional Resources