Skip to content

44. Wildcard Matching

DifficultyHard

Description

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

  • '?' Matches any single character.
  • '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

 

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

 

Constraints:

  • 0 <= s.length, p.length <= 2000
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '?' or '*'.

Solutions

Thinking

The first idea is recurse character by character: literals and ? match one, * eats empty or more. Correct, but without memo the * branches explode. \(|s|, |p| \le 2000\) will time out.

The bottleneck is asking the same suffix pair \((i, j)\) over and over. The state is only “does \(s[i:]\) match \(p[j:]\)”; subproblems overlap heavily.

Cache \(\textit{dfs}(i, j)\). The three * moves (consume one, advance both, skip *) are transitions on that state. Memoization turns exponential search into \(O(mn)\).

We design a function \(\textit{dfs}(i, j)\), which represents whether the string \(s\) starting from the \(i\)-th character matches the string \(p\) starting from the \(j\)-th character. The answer is \(\textit{dfs}(0, 0)\).

The execution process of the function \(\textit{dfs}(i, j)\) is as follows:

  • If \(i \geq \textit{len}(s)\), then \(\textit{dfs}(i, j)\) is true only when \(j \geq \textit{len}(p)\) or \(p[j] = '*'\) and \(\textit{dfs}(i, j + 1)\) is true.
  • If \(j \geq \textit{len}(p)\), then \(\textit{dfs}(i, j)\) is false.
  • If \(p[j] = '*'\), then \(\textit{dfs}(i, j)\) is true if and only if \(\textit{dfs}(i + 1, j)\) or \(\textit{dfs}(i + 1, j + 1)\) or \(\textit{dfs}(i, j + 1)\) is true.
  • Otherwise, \(\textit{dfs}(i, j)\) is true if and only if \(p[j] = '?'\) or \(s[i] = p[j]\) and \(\textit{dfs}(i + 1, j + 1)\) is true.

To avoid repeated calculations, we use the method of memoization search and store the result of \(\textit{dfs}(i, j)\) in a hash table.

The time complexity is \(O(mn)\), and the space complexity is \(O(mn)\), where \(m\) and \(n\) are the lengths of the strings \(s\) and \(p\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def dfs(i: int, j: int) -> bool:
            if i >= len(s):
                return j >= len(p) or (p[j] == "*" and dfs(i, j + 1))
            if j >= len(p):
                return False
            if p[j] == "*":
                return dfs(i + 1, j) or dfs(i + 1, j + 1) or dfs(i, j + 1)
            return (p[j] == "?" or s[i] == p[j]) and dfs(i + 1, j + 1)

        return dfs(0, 0)
 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 {
    private Boolean[][] f;
    private char[] s;
    private char[] p;
    private int m;
    private int n;

    public boolean isMatch(String s, String p) {
        this.s = s.toCharArray();
        this.p = p.toCharArray();
        m = s.length();
        n = p.length();
        f = new Boolean[m][n];
        return dfs(0, 0);
    }

    private boolean dfs(int i, int j) {
        if (i >= m) {
            return j >= n || (p[j] == '*' && dfs(i, j + 1));
        }
        if (j >= n) {
            return false;
        }
        if (f[i][j] != null) {
            return f[i][j];
        }
        if (p[j] == '*') {
            f[i][j] = dfs(i + 1, j) || dfs(i + 1, j + 1) || dfs(i, j + 1);
        } else {
            f[i][j] = (p[j] == '?' || s[i] == p[j]) && dfs(i + 1, j + 1);
        }
        return f[i][j];
    }
}
 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:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<int>> f(m + 1, vector<int>(n + 1, -1));
        function<bool(int, int)> dfs = [&](int i, int j) {
            if (i >= m) {
                return j >= n || (p[j] == '*' && dfs(i, j + 1));
            }
            if (j >= n) {
                return false;
            }
            if (f[i][j] != -1) {
                return f[i][j] == 1;
            }
            if (p[j] == '*') {
                f[i][j] = dfs(i + 1, j) || dfs(i, j + 1) ? 1 : 0;
            } else {
                f[i][j] = (p[j] == '?' || s[i] == p[j]) && dfs(i + 1, j + 1) ? 1 : 0;
            }
            return f[i][j] == 1;
        };
        return dfs(0, 0);
    }
};
 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
func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    var dfs func(i, j int) bool
    dfs = func(i, j int) bool {
        if i >= m {
            return j >= n || p[j] == '*' && dfs(i, j+1)
        }
        if j >= n {
            return false
        }
        if f[i][j] != 0 {
            return f[i][j] == 1
        }
        f[i][j] = 2
        ok := false
        if p[j] == '*' {
            ok = dfs(i+1, j) || dfs(i+1, j+1) || dfs(i, j+1)
        } else {
            ok = (p[j] == '?' || s[i] == p[j]) && dfs(i+1, j+1)
        }
        if ok {
            f[i][j] = 1
        }
        return ok
    }
    return dfs(0, 0)
}
 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
function isMatch(s: string, p: string): boolean {
    const m = s.length;
    const n = p.length;
    const f: number[][] = Array.from({ length: m + 1 }, () =>
        Array.from({ length: n + 1 }, () => -1),
    );
    const dfs = (i: number, j: number): boolean => {
        if (i >= m) {
            return j >= n || (p[j] === '*' && dfs(i, j + 1));
        }
        if (j >= n) {
            return false;
        }
        if (f[i][j] !== -1) {
            return f[i][j] === 1;
        }
        if (p[j] === '*') {
            f[i][j] = dfs(i + 1, j) || dfs(i, j + 1) ? 1 : 0;
        } else {
            f[i][j] = (p[j] === '?' || s[i] === p[j]) && dfs(i + 1, j + 1) ? 1 : 0;
        }
        return f[i][j] === 1;
    };
    return dfs(0, 0);
}
 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
public class Solution {
    private bool?[,] f;
    private char[] s;
    private char[] p;
    private int m;
    private int n;

    public bool IsMatch(string s, string p) {
        this.s = s.ToCharArray();
        this.p = p.ToCharArray();
        m = s.Length;
        n = p.Length;
        f = new bool?[m, n];
        return Dfs(0, 0);
    }

    private bool Dfs(int i, int j) {
        if (i >= m) {
            return j >= n || (p[j] == '*' && Dfs(i, j + 1));
        }
        if (j >= n) {
            return false;
        }
        if (f[i, j] != null) {
            return f[i, j].Value;
        }
        if (p[j] == '*') {
            f[i, j] = Dfs(i + 1, j) || Dfs(i + 1, j + 1) || Dfs(i, j + 1);
        } else {
            f[i, j] = (p[j] == '?' || s[i] == p[j]) && Dfs(i + 1, j + 1);
        }
        return f[i, j].Value;
    }
}
 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
class Solution {
    /**
     * @param string $s
     * @param string $p
     * @return boolean
     */
    private $f;
    private $s;
    private $p;
    private $m;
    private $n;

    function isMatch($s, $p) {
        $this->s = $s;
        $this->p = $p;
        $this->m = strlen($s);
        $this->n = strlen($p);
        $this->f = [];
        for ($i = 0; $i < $this->m; $i++) {
            $this->f[$i] = array_fill(0, $this->n, null);
        }
        return $this->dfs(0, 0);
    }

    function dfs($i, $j) {
        if ($i >= $this->m) {
            return $j >= $this->n || ($this->p[$j] == '*' && $this->dfs($i, $j + 1));
        }
        if ($j >= $this->n) {
            return false;
        }
        if ($this->f[$i][$j] !== null) {
            return $this->f[$i][$j];
        }
        if ($this->p[$j] == '*') {
            $this->f[$i][$j] =
                $this->dfs($i + 1, $j) || $this->dfs($i + 1, $j + 1) || $this->dfs($i, $j + 1);
        } else {
            $this->f[$i][$j] =
                ($this->p[$j] == '?' || $this->s[$i] == $this->p[$j]) && $this->dfs($i + 1, $j + 1);
        }
        return $this->f[$i][$j];
    }
}

Solution 2: Dynamic Programming

Thinking

Solution 1 already fills this match table from shorter prefixes to longer ones. The \(f[i][j]\) below is that same table.

Solution 1 already fills this table from shorter prefixes to longer ones.

Define \(f[i][j]\) to represent whether the first \(i\) characters of string \(s\) match the first \(j\) characters of string \(p\). Initially, \(f[0][0] = \textit{true}\), indicating that two empty strings are matching. For \(j \in [1, n]\), if \(p[j-1] = '*'\), then \(f[0][j] = f[0][j-1]\).

Next, we consider the case of \(i \in [1, m]\) and \(j \in [1, n]\):

  • If \(p[j-1] = '*'\), then \(f[i][j] = f[i-1][j] \lor f[i][j-1] \lor f[i-1][j-1]\).
  • Otherwise, \(f[i][j] = (p[j-1] = '?' \lor s[i-1] = p[j-1]) \land f[i-1][j-1]\).

The final answer is \(f[m][n]\).

The time complexity is \(O(mn)\), and the space complexity is \(O(mn)\), where \(m\) and \(n\) are the lengths of the strings \(s\) and \(p\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0] = True
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                f[0][j] = f[0][j - 1]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == "*":
                    f[i][j] = f[i - 1][j] or f[i][j - 1] or f[i - 1][j - 1]
                else:
                    f[i][j] = f[i - 1][j - 1] and (
                        p[j - 1] == "?" or s[i - 1] == p[j - 1]
                    )
        return f[m][n]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int j = 1; j <= n; ++j) {
            if (p.charAt(j - 1) == '*') {
                f[0][j] = f[0][j - 1];
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j - 1]
                        && (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1));
                }
            }
        }
        return f[m][n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
        f[0][0] = true;
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '*') {
                f[0][j] = f[0][j - 1];
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
                }
            }
        }
        return f[m][n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    f := make([][]bool, m+1)
    for i := range f {
        f[i] = make([]bool, n+1)
    }
    f[0][0] = true
    for j := 1; j <= n; j++ {
        if p[j-1] == '*' {
            f[0][j] = f[0][j-1]
        }
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if p[j-1] == '*' {
                f[i][j] = f[i-1][j] || f[i][j-1] || f[i-1][j-1]
            } else {
                f[i][j] = f[i-1][j-1] && (p[j-1] == '?' || s[i-1] == p[j-1])
            }
        }
    }
    return f[m][n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function isMatch(s: string, p: string): boolean {
    const m: number = s.length;
    const n: number = p.length;
    const f: boolean[][] = Array.from({ length: m + 1 }, () =>
        Array.from({ length: n + 1 }, () => false),
    );
    f[0][0] = true;
    for (let j = 1; j <= n; ++j) {
        if (p.charAt(j - 1) === '*') {
            f[0][j] = f[0][j - 1];
        }
    }
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (p[j - 1] === '*') {
                f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i - 1][j - 1];
            } else {
                f[i][j] = f[i - 1][j - 1] && (p[j - 1] === '?' || s[i - 1] === p[j - 1]);
            }
        }
    }
    return f[m][n];
}
 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
class Solution {
    /**
     * @param string $s
     * @param string $p
     * @return boolean
     */

    function isMatch($s, $p) {
        $m = strlen($s);
        $n = strlen($p);
        $f = [];
        for ($i = 0; $i <= $m; $i++) {
            $f[$i] = array_fill(0, $n + 1, false);
        }
        $f[0][0] = true;
        for ($j = 1; $j <= $n; $j++) {
            if ($p[$j - 1] == '*') {
                $f[0][$j] = $f[0][$j - 1];
            }
        }
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($p[$j - 1] == '*') {
                    $f[$i][$j] = $f[$i - 1][$j] || $f[$i][$j - 1] || $f[$i - 1][$j - 1];
                } else {
                    $f[$i][$j] =
                        $f[$i - 1][$j - 1] && ($p[$j - 1] == '?' || $s[$i - 1] == $p[$j - 1]);
                }
            }
        }
        return $f[$m][$n];
    }
}

Solution 3: Dynamic Programming

Thinking

Matching one character at a time is the natural first idea: a literal or ? consumes one character, and * consumes the empty string or any run. Both strings can have length \(2000\), and the first move on * is always \(\textit{dfs}(i+1, j)\), so that chain is as deep as \(|s|\) and exceeds the default recursion limit.

The same index pair is asked repeatedly, and whether two prefixes match depends only on shorter prefixes.

Let \(f[i][j]\) mean the first \(i\) characters of \(s\) match the first \(j\) characters of \(p\). The empty pair is true, and a run of * on the pattern inherits along \(j\). Filling \(i\) and \(j\) from small to large works because a * reads the cell above, the cell to the left, and the diagonal, while a literal or ? reads only the diagonal.

Define \(f[i][j]\) to represent whether the first \(i\) characters of string \(s\) match the first \(j\) characters of string \(p\). Initially, \(f[0][0] = \textit{true}\), indicating that two empty strings are matching. For \(j \in [1, n]\), if \(p[j-1] = '*'\), then \(f[0][j] = f[0][j-1]\).

Next, we consider the case of \(i \in [1, m]\) and \(j \in [1, n]\):

  • If \(p[j-1] = '*'\), then \(f[i][j] = f[i-1][j] \lor f[i][j-1] \lor f[i-1][j-1]\).
  • Otherwise, \(f[i][j] = (p[j-1] = '?' \lor s[i-1] = p[j-1]) \land f[i-1][j-1]\).

The final answer is \(f[m][n]\).

The time complexity is \(O(mn)\), and the space complexity is \(O(mn)\), where \(m\) and \(n\) are the lengths of the strings \(s\) and \(p\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0] = True
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                f[0][j] = f[0][j - 1]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == "*":
                    f[i][j] = f[i - 1][j] or f[i][j - 1] or f[i - 1][j - 1]
                else:
                    f[i][j] = f[i - 1][j - 1] and (
                        p[j - 1] == "?" or s[i - 1] == p[j - 1]
                    )
        return f[m][n]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int j = 1; j <= n; ++j) {
            if (p.charAt(j - 1) == '*') {
                f[0][j] = f[0][j - 1];
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j - 1]
                        && (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1));
                }
            }
        }
        return f[m][n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        bool f[m + 1][n + 1];
        memset(f, false, sizeof(f));
        f[0][0] = true;
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '*') {
                f[0][j] = f[0][j - 1];
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
                }
            }
        }
        return f[m][n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    f := make([][]bool, m+1)
    for i := range f {
        f[i] = make([]bool, n+1)
    }
    f[0][0] = true
    for j := 1; j <= n; j++ {
        if p[j-1] == '*' {
            f[0][j] = f[0][j-1]
        }
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if p[j-1] == '*' {
                f[i][j] = f[i-1][j] || f[i][j-1] || f[i-1][j-1]
            } else {
                f[i][j] = f[i-1][j-1] && (p[j-1] == '?' || s[i-1] == p[j-1])
            }
        }
    }
    return f[m][n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function isMatch(s: string, p: string): boolean {
    const m: number = s.length;
    const n: number = p.length;
    const f: boolean[][] = Array.from({ length: m + 1 }, () =>
        Array.from({ length: n + 1 }, () => false),
    );
    f[0][0] = true;
    for (let j = 1; j <= n; ++j) {
        if (p.charAt(j - 1) === '*') {
            f[0][j] = f[0][j - 1];
        }
    }
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (p[j - 1] === '*') {
                f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i - 1][j - 1];
            } else {
                f[i][j] = f[i - 1][j - 1] && (p[j - 1] === '?' || s[i - 1] === p[j - 1]);
            }
        }
    }
    return f[m][n];
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length, n = p.Length;
        bool[,] f = new bool[m + 1, n + 1];
        f[0, 0] = true;
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '*') {
                f[0, j] = f[0, j - 1];
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i, j] = f[i - 1, j] || f[i, j - 1] || f[i - 1, j - 1];
                } else {
                    f[i, j] = f[i - 1, j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
                }
            }
        }
        return f[m, n];
    }
}
 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
class Solution {
    /**
     * @param string $s
     * @param string $p
     * @return boolean
     */

    function isMatch($s, $p) {
        $m = strlen($s);
        $n = strlen($p);
        $f = [];
        for ($i = 0; $i <= $m; $i++) {
            $f[$i] = array_fill(0, $n + 1, false);
        }
        $f[0][0] = true;
        for ($j = 1; $j <= $n; $j++) {
            if ($p[$j - 1] == '*') {
                $f[0][$j] = $f[0][$j - 1];
            }
        }
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($p[$j - 1] == '*') {
                    $f[$i][$j] = $f[$i - 1][$j] || $f[$i][$j - 1] || $f[$i - 1][$j - 1];
                } else {
                    $f[$i][$j] =
                        $f[$i - 1][$j - 1] && ($p[$j - 1] == '?' || $s[$i - 1] == $p[$j - 1]);
                }
            }
        }
        return $f[$m][$n];
    }
}

Comments