[LeetCode] 44. Wildcard Matching

https://leetcode.com/

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

 

Code :

var isMatch = function(s, p) {
    let sIndex = 0, pIndex = 0, match = 0, starIndex = -1;
    
    // 주어진 문자열 s를 기반으로 주어진 패턴 p와 일치하는지 확인
    while (sIndex < s.length) {
        if (pIndex < p.length && (p[pIndex] === '?' || s[sIndex] === p[pIndex])) {
            // 현재 패턴이 '?'이거나 문자가 일치하면 다음 문자로 이동
            sIndex++;
            pIndex++;
        } else if (pIndex < p.length && p[pIndex] === '*') {
            // '*'을 만나면 해당 위치와 일치하는 문자의 인덱스를 저장하고 패턴 인덱스를 증가
            starIndex = pIndex;
            match = sIndex;
            pIndex++;
        } else if (starIndex !== -1) {
            // '*' 이후 일치하지 않는 경우 이전에 저장한 정보를 사용하여 다시 매칭
            pIndex = starIndex + 1;
            match++;
            sIndex = match;
        } else {
            // '*'이 아니고 일치하지 않는 경우 false 반환
            return false;
        }
    }
    
    // 문자열 s를 다 소모한 경우, 패턴 p가 '*'로만 이루어진 경우를 제외하고 true 반환
    while (pIndex < p.length && p[pIndex] === '*') {
        pIndex++;
    }
    
    return pIndex === p.length;
};

 

Solutions Code :

var isMatch = function(s, p) {
    let string = 0, pattern = 0;
    let starIdx = -1, pointer = -1;

    // 문자열 s와 패턴 p를 비교하여 일치하는지 확인
    while (string < s.length) {
        if ((pattern < p.length && s[string] === p[pattern]) || p[pattern] === "?") {
            // 현재 문자가 일치하거나 패턴이 '?'일 때 문자와 패턴을 하나씩 이동
            string++;
            pattern++;
        } else if (pattern < p.length && p[pattern] === "*") {
            // '*'을 만난 경우 해당 위치와 문자열의 위치를 저장하고 패턴 인덱스 증가
            starIdx = pattern;
            pointer = string;
            pattern++;
        } else if (starIdx === -1) {
            // '*'이 아니고 일치하지 않는 경우 false 반환
            return false;
        } else {
            // '*' 이후 일치하지 않는 경우 저장한 정보를 이용하여 다시 매칭
            pattern = starIdx + 1;
            string = pointer + 1;
            pointer = string;
        }
    }
    
    // 문자열 s를 다 소모한 후 패턴 p가 '*'로만 이루어진 경우를 제외하고 true 반환
    for (let idx = pattern; idx < p.length; idx++) {
        if (p[idx] !== "*") return false;
    }
    return true;
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode