LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 문자열 s, 문자열 p
2. output: 패턴 p가 s 전체와 일치하는지 여부 리턴
   • '?' Matches any single character.
   • '*' Matches any sequence of characters (including the empty sequence).
   • <= s.length, p.length <= 2000
   • s contains only lowercase English letters.
   • p contains only lowercase English letters, '?' or '*'.

Idea

앞에서 부터 두 문자열이 일치하는지 단순히 확인하고 싶지만 ‘*’에 따라서 분기가 생기고, 단순히 탐색할 경우 시간초과에 걸린다. → DP를 사용하여야 한다.

평소 자주 사용했던 Bottom-Up(Tabulation)으로 통과했다. → Sol1

중요하게 고려해야할 문자는 ‘’, 특히 처음에 ‘’이 오는 경우만 조심하면 된다.

Solution

1. DP

   일반적인 문자의 경우

   • p[idx] == s[idx] → true
   • p[idx] == ‘?’ → true

   ‘*’이 나타나 경우

   • ‘*’이 하나 이상의 문자를 매칭 → dp[p][s-1]를 따라감

     ex) s = “abcdefg”, p = “ab*”

   • ‘*’이 0개의 문자 매칭 → dp[p-1][s] 를 따라감

     ex) s = “abcd”, p = “abcd*”

     ⇒ ‘*’이 p의 가장 처음으로 등장하는 경우를 위해 dp의 첫열을 true로 채워줘야함

     for (i in p.*indices*) if (p[i] == '*') dp[i+1][0] = true else break

   class Solution {
       fun isMatch(s: String, p: String): Boolean {
           val a = hashMapOf<Int, Int>()
           val dp = Array<Array<Boolean>>(p.length + 1) { Array<Boolean>(s.length + 1) { false } }
           dp[0][0] = true
           // p의 처음부터 *이 나타나는 경우 대비, 처음 * 갯수만큼 true로 채워줌
           for (i in p.indices) if (p[i] == '*') dp[i+1][0] = true else break
           for (pIdx in p.indices) {
               for (sIdx in s.indices) {
                   if (p[pIdx] == '*') {
                       // *이 0개 문자 매칭 or 1개 이상 문자 매칭
                       if (dp[pIdx+1][sIdx] || dp[pIdx][sIdx+1]) dp[pIdx+1][sIdx+1] = true
                   } else {
                       // p가 s와 일치하거나 ?
                       if ((p[pIdx] == '?' || p[pIdx] == s[sIdx]) && dp[pIdx][sIdx]) {
                           dp[pIdx+1][sIdx+1] = true
                       }
                   }
               }
           }
           return dp[p.length][s.length]
       }
   }
   

   시간 복잡도: 문자열 순회 X 문자열 순회 = n^2

   

Point

1. 그냥 탐색으로 시간 초과 + 반복되는 작업 포함 = DP
   • 점화식/규칙 찾기
   • Top-Down(Memoization) vs Bottom-Up(Tabulation) 결정