정규식 관련 문제였어요. 아쉽게도 이번엔 풀지 못해서 답을 보았습니다...

문제

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

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

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

제한사항

Constraints:

• $1 \leq s.length \leq 20$
• $1 \leq p.length \leq 30$
• s contains only lowercase English letters.
• p contains only lowercase English letters, '.', and '*'.
• It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

접근

LeetCode가 제공하는 Solution을 참고하였어요(실은 거의 베꼈어요).

재귀함수를 통해 부분 문자열 간에 비교한 로직이었습니다.

백신 맞아서 그런지 상태가 좋지 않네요...일단 답만 적어두고 이후에 다시 봐야겠어요

답안1

class Solution {
    public boolean isMatch(String s, String p) {
        if(p.isEmpty()) return s.isEmpty();

        boolean firstMath = (!s.isEmpty() &&
                            (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));
        
        if(p.length() >= 2 && p.charAt(1) == '*'){
            return (isMatch(s, p.substring(2)) ||
                    (firstMath && isMatch(s.substring(1), p)));
        }
        return (firstMath && isMatch(s.substring(1), p.substring(1)));
    }
}