LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 문자열 s, 찾는 패턴 p
2. output: 문자열 s가 패턴 p와 일치하는 지 여부 리턴
3. 패턴은 문자열 전체와 일치해야함
   • '.' Matches any single character.
   • '*' Matches zero or more of the preceding element.

Idea

1. 정규표현식 ⭕

   class Solution {
       fun isMatch(s: String, p: String): Boolean {
           return s.matches(p.toRegex())
       }
   }
   

   시간 복잡도:

   

2. DP테이블을 통해 매칭 여부 판단 ⭕

   • 이 나타나는 경우만 조심하면 됨
   • 앞의 문자 1번 이상 사용 → 패턴 한칸 앞자리와 일치 여부 확인
   • 앞의 문자 사용 X → 패턴 두칸 앞자리까지 일치 여부 확인

   class Solution {
       fun isMatch(s: String, p: String): Boolean {
           val dp = Array(s.length + 1){BooleanArray(p.length + 1)}
   dp[0][0] = true
           // j= 0 자리 초기화
           for (i in 1..s.length) {
               dp[i][0] = false
           }
           // i = 0 자리 초기화
           for (j in 1..p.length) {
               if (p[j - 1] == '*') { // 패턴의 2번째 자리에 바로 *이 오는 경우 대비
                   dp[0][j] = dp[0][j - 2]
               } else {
                   dp[0][j] = false
               }
           }
           // 한칸씩 매칭
           // 패턴이 더 짧을 수도 있고, 패턴에 *에 따라 다시 비교해야하므로 j -> i 순으로 비교
           for (i in 1..s.length) {
               for (j in 1..p.length) {
                   if (s[i - 1] == p[j - 1] || p[j - 1] == '.') { // 현재 idx 문자가 일치하는 경우
                       dp[i][j] = dp[i - 1][j - 1] // 이전 일치 여부 따라감
                   } else if (p[j - 1] == '*') {
                       // * 앞의 문자 한개도 안씀  OR  앞의 문자 사용
                       dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'))
                   }
               }
           }
           return dp[s.length][p.length]
       }
   }
   

   시간 복잡도: s 순회 X p 순회 = n^2

   

Point

1. dp[0][0] = True를 위해 dp의 인덱스, 문자열과 1씩 차이남