[algospot][WILDCARD] Wildcard

문제 : https://algospot.com/judge/problem/read/WILDCARD

---

DP로 풀었다.

dp[i][j] = pattern[i~끝] 부분문자열과 s[j~끝] 부분문자열이 같은가(같으면 1, 다르면 0, 아직 탐색 전이면 -1)

패턴문자열(pattern)과 패턴에 맞는지 확인하고자 하는 문자열(s)가 있다고 할 때 DP에 사용할 배열은 위와 같이 나타낼 수 있다.

 

패턴 문자열에 올 수 있는 문자는 '*', '?', 알파벳이다.

만약 알파벳이라면 pattern[i]와 s[j]가 같은지 체크하고 다르면 false를 반환, 같다면 i+1, j+1 부터 다시 탐색해간다.

'?' 인 경우 s[j] 가 어떤 문자가 오던지 정답이 가능하므로 i+1, j+1 부터 다시 탐색해나간다.

'*' 인 경우 for문을 돌리면서 i+1, j+k (0 <= k <= s문자열 길이 - j) 를 탐색하고 하나라도 정답이 가능하다면 true, 전부 불가능하다면 false를 반환한다.

k는 무시하고자 하는 s문자열에서 문자 수를 의미한다. 즉, 0개를 무시할 것인지부터 모든 남은 s문자열을 무시할 것인지를 모두 탐색한다.

 

종료조건은 i, j가 동시에 각 문자열의 끝에 도착하는 경우 정답이 가능한 경우이다.

만약 i, j 중 하나라도 탐색 인덱스를 벗어난다면 정답이 불가능하다.

 

시간 복잡도는 dp 배열을 채우는데 소요되는 시간으로 O(|pattern||s|) 이다.

각 문자열은 최대 길이가 100이므로 하나의 문자열을 탐색할 때 패턴에 적합한지 탐색하는데 소요되는 최대 시간은 100*100이 되므로 제한조건 내에 충분히 가능한 시간이다.

 

---

소스코드 : https://gist.github.com/fpdjsns/f10f78fdc1dc148fb5f658f2eb5ecff5