Code Monkey home page Code Monkey logo

Comments (3)

duziaqin avatar duziaqin commented on June 9, 2024 3

需要对.的情况再限制一下，不然在遭遇isMatch('ab', '.*c')会陷入死循环
另外返回值要求布尔值，需要稍微转一下

function isMatch(s, p) {
    if (!s && !p) return true
    if (p && p[1] === '*') {
        return !!(
            isMatch(s, p.slice(2)) ||
            (s[0] === p[0] || (p[0] === '.' && s[0])) && isMatch(s.slice(1), p)
        )
    } else {
        return !!(
            (s[0] === p[0] || (p[0] === '.' && s[0])) && isMatch(s.slice(1), p.slice(1))
        )
    }
}

from daily-algorithms.

barretlee avatar barretlee commented on June 9, 2024 1

这道题看起来还是比较复杂的，可能出现的情况很多，不过可以通过 * 来入手分析，不管是什么字符，即便是 .，如果后面跟着的不是 *，那么匹配起来是很轻松的，可以如下穷举：

  • s 为 null，p 为 null，返回 true；
  • p[1] 等于 *，前部分匹配为空，则 p 前两个字符无效；前部分匹配一个字符，则进入下一次递归；
  • p[1] 不等于 *，那么只需要对比第一个字符就行了，匹配通过的话，s 和 p 的前一个字符就无效了，进入下一次递归。

具体实现如下：

function isMatch(s, p) {
  if (!s && !p) return true;
  if (p && p[1] === '*') {
    return (
      // Skip First Token, Match next token
      isMatch(s, p.slice(2)) || 
      // Matched First Token, Match next token
      (s[0] === p[0] || p[0] === '.') && isMatch(s.slice(1), p)
    );
  } else {
    return (
      // Matched First Token, Match next token
      (s[0] === p[0] || p[0] === '.') && isMatch(s.slice(1), p.slice(1))
    );
  }
}

console.assert(isMatch('aa', 'a') === false, 1);
console.assert(isMatch('aa', 'aa') === true, 2);
console.assert(isMatch('aaa', 'aa') === false, 3);
console.assert(isMatch('aa', 'a*') === true, 4);
console.assert(isMatch('aa', '.*') === true, 5);
console.assert(isMatch('ab', '.*') === true, 6);
console.assert(isMatch('aab', 'c*a*b') === true, 7);

from daily-algorithms.

YabZhang avatar YabZhang commented on June 9, 2024 
def is_match(string, pattern):
    """
     1. `.`匹配任何单字；2. `*`匹配０个或多个字符；
    """
    if not string and not pattern:
        return True
    
    # `*` match blank string 
    if not string and not pattern.replace('*', ''):
        return True

    if not pattern or not string:
        return False

    if pattern[0] == '*':
        return is_match(string[1:], pattern) or is_match(string, pattern[1:])
    else:
        if pattern[0] != string[0]:
            if pattern[0] != '.':
                return False
        return is_match(string[1:], pattern[1:])


if __name__ == '__main__':
    assert is_match('aa', 'a') == False
    assert is_match('aa', 'aa') == True
    assert is_match('aaa', 'aaa') == True
    assert is_match('aaa', '.a') == False
    assert is_match('aa', '.*') == True
    assert is_match('aab', '*') == True
    assert is_match('b', '.*.') == False

from daily-algorithms.

Related Issues (16)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.