LeetCode 10. Regular Expression Matching

LeetCode Problem No.10.

No.9 is here.

modalsoul.hatenablog.com

10. Regular Expression Matching

https://leetcode.com/problems/regular-expression-matching/

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

'.' Matches any single character. '*' Matches zero or more of the preceding element.

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 = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Code

object Solution {
    def charMatch(s:String, p:String) = !s.isEmpty && (p.head == s.head || p.head == '.')
    def isMatch(s: String, p: String): Boolean = {
        if(p.isEmpty) s.isEmpty
        else if(p.length >= 2 && p.tail.head == '*') isMatch(s, p.drop(2)) || charMatch(s, p) && isMatch(s.tail, p)
        else charMatch(s, p) && isMatch(s.tail, p.tail)
    }
}

Methods

• If next pattern char is '*', check these cases.
  • Matching zero of the preceding element.
  • Matching more of the preceding element.
    • Compare string head char and pattern head char and check rest matching.
• If next patter char is not '*', compare string head char and pattern head char and check rest matching.

Results

Runtime: 600 ms, faster than 34.61% of Scala online submissions for Regular Expression Matching. Memory Usage: 54.4 MB, less than 100.00% of Scala online submissions for Regular Expression Matching.