44. Wildcard Matching (Hard)

https://leetcode.com/problems/wildcard-matching/

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

Solutions

class Solution {

    // Used to keep the matching results of already compared strings, otherwise,
    // it will exceeds time limit.
    Map<String, Boolean> track = new HashMap<>();

    public boolean isMatch(String s, String p) {
        if (s == null) {
            s = "";
        }

        if (p == null) {
            p = "";
        }

        String np = "";
        char pre = 0;

        // process p to merge consecutive *
        for (int i = 0; i < p.length(); i++) {

            // initialize the start condition
            if (i == 0) {
                np += p.charAt(0);
                pre = p.charAt(0);

                continue;
            }

            if (p.charAt(i) == pre && pre == '*') {
                continue;
            }

            // if not consecutive *, move on
            np += p.charAt(i);
            pre = p.charAt(i);
        }

        return check(s, np);
    }

    private boolean check(String s, String p) {
        /*
            // if two string match, return immediately
            if (isFound) {
                return isFound;
            }
        */

        boolean ans = false;

        if (s.length() == 0 && p.length() == 0) {
            return true;
        }

        if (s.length() != 0 && p.length() == 0) {
            return false;
        }

        if (track.containsKey(s + "#" + p)) {
            return track.get(s + "#" + p);
        }

        if (s.length() == 0 && p.length() != 0) {

            // After processing, p will not contain consecutive *, in other words, if p.length() > 1
            // there must be some other chars that need to be matching 1 by 1. Since s.length() is 0,
            // nothing to compare. Only if p.length() == 1 and p[0] = '*', p and s can match perfectly.

            if (p.length() == 1 && p.charAt(0) == '*') {
                ans = true;
            } else {
                ans = false;
            }

            track.put(s + "#" + p, ans);

            return ans;
        }

        // To reach here, s.length and p.length both >= 1

        // count chars except *
        int charCount = 0;
        for (int i = 0; i < p.length(); i++) {
            if (p.charAt(i) != '*') {
                charCount++;
            }
        }

        // if p contains more regular chars, impossible to match them all
        if (charCount > s.length()) {
            ans = false;

            track.put(s + "#" + p, ans);

            return ans;
        }

        // if p[0] != '.' and '*', test if p[0] == s[0]
        if (p.charAt(0) != '?' && p.charAt(0) != '*') {

            if (s.charAt(0) != p.charAt(0)) {
                // return false if not match

                ans = false;
            } else {
                // check recursively if match

                ans = check(s.substring(1), p.substring(1));
            }

            track.put(s + "#" + p, ans);

            return ans;
        }

        // if p[0] == '.', no need to test if p[0] == s[0]
        // move on to compare s[1:] p[1:]
        if (p.charAt(0) == '?') {
            ans = isMatch(s.substring(1), p.substring(1));

            track.put(s + "#" + p, ans);

            return ans;
        }

        // if p[0] == '*', three situations,

        // 1. compare s[], p[1:] which means p[0] covers zero char

        // 2. s[1:] p[1:] which p[0] covers 1 char and its coverage ends here.

        // 3. compare s[1:], p[:] which means p[0] matches at least 2 chars and
        // the followup letters will still be covered.

        if (p.charAt(0) == '*') {
            // p[0] counts for 0 char
            ans = ans || check(s, p.substring(1));

            // p[0] counts for 1 char
            ans = ans || check(s.substring(1), p.substring(1));

            // p[0] counts for at least 2 char
            ans = ans || check(s.substring(1), p);
        }

        // any true results of above three matching test will result in a final true

        track.put(s + "#" + p, ans);

        return ans;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""