[C++] 알고스팟/동적계획법 - 와일드카드

문제 링크

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

algospot.com :: WILDCARD

 

먼저 와일드카드에 * 가 없는 경우에는 두 문자열을 비교하기가 쉽습니다.

두 문자열의 첫번째 인덱스부터 비교하여 두 문자가 같거나 와일드카드가 ? 인 경우는 다음 인덱스를 재귀함수로 넘겨서 확인하면 됩니다.

 

하지만 와일드카드에 * 가 포함되면 * 에 문자열이 얼마나 대응하는지를 확인해야 합니다.

 

위와 같은 와일드카드가 있을 때 첫 번째 papa 는 왼쪽 * 가 0개 오른쪽 * 가 apa에 대응하고

두 번째 papa는 왼쪽 * 가 pa, 오른쪽 * 가 a에 대응합니다.

 

따라서 와일드카드의 현재 인덱스가 * 이면

1. 와일드카드 현재 인덱스 + 1, 비교문자열 현재 인덱스

2. 와일드카드 현재 인덱스, 비교문자열 현재 인덱스+1

 

이 두가지 경우를 재귀함수로 탐색해서 다음 각 문자들을 비교해 나가야합니다.

1번은 * 가 아무것도 대응하지 않는 경우이고

2번은 * 가 1개 이상의 문자에 대응하는 경우입니다.

 

 

구현 코드