Problem Explanation

This problem involves string pattern matching with wildcard characters. The aim is to write a function isMatch which determines if an input string (s) fully matches a given pattern (p).

In the pattern string, two types of wildcard characters are supported:

• '?' which matches any single character.
• '*' which matches any sequence of characters including an empty sequence.

The function needs to return a boolean output indicating if the input string entirely, and not partially, matches the pattern. If it does match, the function returns True else it returns False.

For instance, given Input:

1
2
3s = "aa"
4p = "a"

The function should return False because 'a' does not match the entire string 'aa'. Similarly, for Input:

1
2
3s = "adceb"
4p = "*a*b"

The function should return True as the first '' matches the empty sequence, while the second '' matches the substring "dce".

Solution Approach

The solution to this problem uses the concept of Dynamic Programming. A 2D Boolean array dp[i][j] is initialized where dp[i][j] is True if s[0..i) matches p[0..j). Initially, dp[0][0] is set to True indicating that two empty strings are a match.

An inline function isMatch(i, j) is defined that checks whether a character in string s matches with a character or '?' in pattern p.

Next, we run a loop over the pattern string and for every '*', dp[0][j+1] is set to dp[0][j].

Then, we run a nested loop through the string lengths of input s and pattern p.

For every '', there can be two cases - matching an empty sequence or matching some sequence. matchEmpty checks if '' matches an empty sequence and matchSome checks if '*' matches some sequence in string s. dp[i + 1][j + 1] is updated as per these conditions.

If character/pattern is not '*', then dp[i + 1][j + 1] is simply updated to dp[i][j] if the string and pattern characters match.

Finally, dp[m][n] is returned which indicates whether entire string s matches pattern p or not.

Python Solution

1
2python
3class Solution:
4    def isMatch(self, s: str, p: str) -> bool:
5        m = len(s)
6        n = len(p)
7        dp = [[False]*(n+1) for _ in range(m+1)]
8        dp[0][0] = True
9        for j in range(1, n+1):
10            if p[j-1] == '*':
11                dp[0][j] = dp[0][j-1]
12        for i in range(1, m+1):
13            for j in range(1, n+1):
14                if p[j-1] == '*':
15                    dp[i][j] = dp[i][j-1] or dp[i-1][j]
16                elif p[j-1] == '?' or s[i-1] == p[j-1]:
17                    dp[i][j] = dp[i-1][j-1]
18        return dp[m][n]

Java Solution

1
2java
3class Solution {
4    public boolean isMatch(String s, String p) {
5        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
6        dp[0][0] = true;
7        for (int j = 1; j <= p.length(); j++) {
8            if (p.charAt(j-1) == '*') {
9                dp[0][j] = dp[0][j-1];
10            }
11        }
12        for (int i = 1; i <= s.length(); i++) {
13            for (int j = 1; j <= p.length(); j++) {
14                if (p.charAt(j-1) == '*') {
15                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
16                } else if (p.charAt(j-1) == '?' || s.charAt(i-1) == p.charAt(j-1)) {
17                    dp[i][j] = dp[i-1][j-1];
18                }
19            }
20        }
21        return dp[s.length()][p.length()];
22    }
23}

JavaScript Solution

1
2javascript
3var isMatch = function(s, p) {
4    let m = s.length, n = p.length;
5    let dp = Array(m+1).fill().map(() => Array(n+1).fill(false));
6    dp[0][0] = true;
7    for (let j = 1; j <= n; j++) {
8        if (p[j-1] === '*') {
9            dp[0][j] = dp[0][j-1];
10        }
11    }
12    for (let i = 1; i <= m; i++) {
13        for (let j = 1; j <= n; j++) {
14            if (p[j-1] === '*') {
15                dp[i][j] = dp[i][j-1] || dp[i-1][j];
16            } else if (p[j-1] === '?' || s[i-1] === p[j-1]) {
17                dp[i][j] = dp[i-1][j-1];
18            }
19        }
20    }
21    return dp[m][n];
22};

C# Solution

1
2csharp
3public class Solution {
4    public bool IsMatch(string s, string p) {
5        int m = s.Length, n = p.Length;
6        bool[,] dp = new bool[m+1,n+1];
7        dp[0,0] = true;
8        for (int j = 1; j <= n; j++) {
9            if (p[j-1] == '*') {
10                dp[0,j] = dp[0,j-1];
11            }
12        }
13        for (int i = 1; i <= m; i++) {
14            for (int j = 1; j <= n; j++) {
15                if (p[j-1] == '*') {
16                    dp[i,j] = dp[i,j-1] || dp[i-1,j];
17                } else if (p[j-1] == '?' || s[i-1] == p[j-1]) {
18                    dp[i,j] = dp[i-1,j-1];
19                }
20            }
21        }
22        return dp[m,n];
23    }
24}

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool isMatch(string s, string p) {
6        int m = s.length(), n = p.length();
7        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
8        dp[0][0] = true;
9        for (int j = 1; j <= n; j++) {
10            if (p[j - 1] == '*') {
11                dp[0][j] = dp[0][j - 1];
12            }
13        }
14        for (int i = 1; i <= m; i++) {
15            for (int j = 1; j <= n; j++) {
16                if (p[j - 1] == '*') {
17                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
18                } 
19                else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
20                    dp[i][j] = dp[i - 1][j - 1];
21                }
22            }
23        }
24        return dp[m][n];
25    }
26};

In the solutions above, the dynamic programming technique is applied to check character by character, including wildcards, if the string s is matched with the pattern p.# Time and Space Complexity Analysis

The time complexity of matching s with the wildcard pattern p is O(m*n), where m and n are the lengths of the string and the pattern respectively. This is because we need to fill up a matrix of size (m + 1) × (n + 1) and filling each of the m*n cells in the matrix requires constant time.

The space complexity for the dynamic programming matrix is also O(m*n). Each entry dp[i][j] requires constant space and thus total space is proportional to the total number of cells, which are m*n.

Application of the Wildcard Matching Problem

The wildcard pattern matching problem can have wide range of applications, including in search engines, databases, algorithms related to biological sequence alignment and many other areas where pattern matching are critical. For example:

• Search Engines: When we perform a google search, we don't know the exact phrase or keyword we're looking for. That's where wildcard pattern matching comes into play. It can be used to match partial queries with the complete data.

• Databases: SQL uses wildcard characters in the LIKE operator for pattern matching in the query.

• Bioinformatics: In biological sequence alignment, dynamic programming algorithms are used to align DNA, RNA and proteins sequences. These algorithms often involve wildcard matches.

In nutshell, the wildcard matching problem is a crucial and fundamental problem in the world of computing, and having understanding on how to efficiently solve it using techniques like dynamic programming broadens your toolbox as a programmer or computer scientist.