Leetcode solution 44: WildcardMatching

原文链接

https://blog.baozitraining.org/2019/04/leetcode-solution-44-wildcard-matching.html

Problem Statement

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

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

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

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like ? or *.

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'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

It seems an easy problem first using recursion and brute forcefully solving the problem, but the OJ will quickly throw a TLE (Time Limit Exceeded) error since it is exponential time. Well, if you were like me, tried really hard to optimize my brute force solution, either using some heuristics or pruning on the recursion, however, still no luck :( DP (Dynamic Programming) is normally a great way when trying to answer below two types of questions, and string related questions are a majority use case of DP

  • Only Yes/No, True/False question without returning detailed step by step results
  • Extreme values, e.g., Max, Min, Best optimal value

I have posted several videos on how to solve DP problems using a template, essentially

  1. Initialize your lookup array, could be 2 dimensional or 1 dimensional using rolling arrays
  2. Initialize the init values in your array
  3. Get the math formula for a[i] = a[i-1] * m - n or whatever condition you need
  4. Code it up

You can find the video tutorial on this problem here

Solutions

Brute force recursion, TLE

public boolean isMatchTLE(String s, String p) {

if (s == null || p == null) {

return false;

}

return isMatchHelper(s, 0, p, 0);

}

// b*b*ab**ba*b**b***bba , this should trim some of the recursion time

public String removeDuplicateStars(String p) {

String newP = "";

for (int i = 0; i < p.length(); i++) {

if (p.charAt(i) != '*') {

newP += p.charAt(i);

} else {

if (newP.length() == 0 || newP.charAt(newP.length() - 1) != '*') {

newP += "*";

}

}

}

return newP;

}

// Even after all those optimizations, this would still TLE, n*2^m

private boolean isMatchHelper(String s, int i, String p, int j) {

if (j == p.length()) {

return i == s.length();

}

p = this.removeDuplicateStars(p);

if (p.charAt(j) == '*') {

// s = "abcdef"

// p = "*bc*def"

if (isMatchHelper(s, i, p, j + 1)) {

return true;

}

if (i == s.length() - 1 && j == p.length() - 1) {

return true;

}

for (int k = i + 1; k < s.length(); k++) {

return isMatchHelper(s, k, p, j);

}

} else {

if (isCharMatch(s, i, p, j)) {

return isMatchHelper(s, i + 1, p, j + 1);

}

return false;

}

return false;

}

// compare if char is the same or it is a '?'

private boolean isCharMatch(String s, int i, String p, int j) {

if (i >= s.length() || j >= p.length()) {

return false;

}

return s.charAt(i) == p.charAt(j) || p.charAt(j) == '?';

}

view rawbruteforce.java hosted with ❤ by GitHub

Time Complexity: assuming S length is M, P length is N, this is O(M*2^N), exponential basically Space Complexity: No extra space needed other than the additional recursion function stack

DP solution

// This is the DP solution, and falls perfectly using the DP template

// Also this is only boolean answer (not find all steps) || find the extreme values (min,max)

public boolean isMatch(String s, String p) {

if (s == null || p == null) {

return false;

}

int row = s.length();

int col = p.length();

boolean[][] lookup = new boolean[row + 1][col + 1];

lookup[0][0] = true;

// initialize lookup init values, for the string (s) part, it all default to false

// since a char matches to empty is false anyway

for (int j = 1; j <= col; j++) {

if (p.charAt(j - 1) == '*' && lookup[0][j - 1]) {

lookup[0][j] = true;

}

}

for (int i = 1; i <= row; i++) {

for (int j = 1; j <= col; j++) {

if (p.charAt(j - 1) == '*') {

lookup[i][j] = lookup[i][j - 1] || lookup[i - 1][j];

} else {

if (lookup[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?')) {

lookup[i][j] = true;

}

}

}

}

return lookup[row][col];

}

view rawwildcardMatching.java hosted with ❤ by GitHub

Time Complexity: assuming S length is M, P length is N, this is O(M*N) because all we need to do is build up that lookup matrix Space Complexity: assuming S length is M, P length is N, this is O(M*N), again, that lookup matrix

References

  • A good DP video tutorial
  • Grandyang very funny writings in Chinese
  • Yu's garden, a not very well explained but very clever(hacky) solution

原文发布于微信公众号 - 包子铺里聊IT(baozitraining)

原文发表时间:2019-04-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券