[Java] LeetCode 10번 Regular Expression Matching

1. dp를 사용하지 않는 풀이

isMatch 함수를 재귀적으로 호출하여 문제를 해결해보았다. 각각의 경우의 수는 주석으로 남겨두었다. 

생각보다 복잡하고, 코드가 길어졌다. dp를 사용하지 않기 때문에 중복으로 같은 케이스를 확인하게 되므로 느리다.

class Solution {
    public boolean isMatch(String s, String p) {
        boolean isPossible = false;
        // s가 남았는데 p가 없는 경우
        if (s.length() > 0 && p.length() == 0) {
            return false;
        }
        // s와 p가 모두 소진된 경우
        else if (s.length() == 0 && p.length() == 0) {
            return true;
        }

        if (p.length() > 1) {
            // 1. 뒤에 *가 있는 경우
            if (p.charAt(1) == '*') {
                // 1.1 p가 .인 경우
                if (p.charAt(0) == '.') {
                    // p를 건너뛰는 경우
                    isPossible |= isMatch(s, p.substring(2));

                    // 매칭하고 지나가는 경우
                    if (s.length() == 0) {
                        isPossible |= false;
                    } else {
                        isPossible |= isMatch(s.substring(1), p);
                    }
                }
                // 1.2 p가 문자인경우
                else {
                    // p를 건너뛰는 경우
                    isPossible |= isMatch(s, p.substring(2));
                    // 매칭하고 지나가는 경우
                    if (s.length() == 0) {
                        isPossible |= false;
                    } else if (p.charAt(0) == s.charAt(0)) {
                        isPossible |= isMatch(s.substring(1), p);
                    }
                }
            }
            // 2. 뒤에 *가 없는 경우
            else {
                // 2.0 s의 길이가 0인 경우는 불가능 함
                if (s.length() == 0) {
                    isPossible |= false;
                }
                // 2.1 p가 .인 경우
                else if (p.charAt(0) == '.') {
                    isPossible |= isMatch(s.substring(1), p.substring(1));
                }
                // 2.2 p가 문자인경우
                else if (p.charAt(0) == s.charAt(0)) {
                    isPossible |= isMatch(s.substring(1), p.substring(1));
                }
                // 2.3 p와 s가 일치하지 않는 경우
                else {
                    isPossible |= false;
                }
            }
        }
        // p가 문자 하나밖에 안남은 경우
        else {
            // 매칭할 s가 없으면 flase
            if (s.length() == 0) {
                isPossible |= false;
            }
            // p가 . 인경우
            else if (p.charAt(0) == '.') {
                isPossible |= isMatch(s.substring(1), p.substring(1));
            }
            // p가 일치하는 경우
            else if (s.charAt(0) == p.charAt(0)) {
                isPossible |= isMatch(s.substring(1), p.substring(1));
            }
        }
        return isPossible;
    }
}

2. dp를 사용한 풀이

dp[si][pi]에 si번째까지의 문자열이 pi번째까지의 패턴과 매칭이 되는지 여부를 저장한다. dp[0][0] = true로 초기값을 기정하기 위해서 문자열을 세는 순서는 0번째부터가 아닌 1번째*부터 시작이되는 것으로 하였다. dp[sLen][pLen]이 우리가 구하고자하는 값이 된다.

si, pi에서 문자가 매칭이 되는 경우에는 dp[si][pi] = dp[si - 1][pi - 1] 이 된다. 왜냐하면 si -1 번째와 pi -1 번째까지 매칭되었다면 dp[si][pi]가 매칭되기 때문이다.

만약 * 이라면 dp[si][pi] 는 1) 매칭을 하지 않고 건너 뛰는 경우 dp[si][pi - 2] 이 될 수도 있고 2) 계속 매칭하는 경우 dp[si - 1][pi] 의 결과의 합이 된다. 

s의 길이가 0일 때도 pattern에 * 이 있는 경우에는 true가 될 수 있어서 이부분을 초반에 계산 해주고, 이후에 s의 길이가 있는 것들을 계산해준다.

1번째* : 올바른 맞춤법으로는 첫번째로 적는것이 맞지만 혼동을 피하기 위해서 1번째라고 표기하였다.

class Solution {
    public boolean isMatch(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();

        boolean[][] dp = new boolean[sLen + 1][pLen + 1];
        dp[0][0] = true;
        for (int j = 2; j <= pLen; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        for (int i = 1; i <= sLen; i++) {
            for (int j = 1; j <= pLen; j++) {
                char sChar = s.charAt(i - 1);
                char pChar = p.charAt(j - 1);
                if (sChar == pChar || pChar == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pChar == '*') {
                    // skip matching
                    dp[i][j] = dp[i][j - 2];

                    // matching
                    char pPrevChar = p.charAt(j - 2);
                    if (pPrevChar == sChar || pPrevChar == '.') {
                        dp[i][j] |= dp[i - 1][j];
                    }
                }
            }
        }
        return dp[sLen][pLen];
    }
}