[Leetcode] 936. Stamping The Sequence

문제 : https://leetcode.com/problems/stamping-the-sequence/

---

이전에 찍힌 스탬프는 덮히고 가장 마지막에 찍히는 스탬프가 최종 글자가 된다.

따라서 뒤에 찍힐수록 중요하게 봐야하는 값이 되므로 스탬프가 찍히는 역순으로 생각한다.

예를 들어 stamp="abc", target="ababc"라면 2번째 자리에 "abxxx" 로 x자리가 스탬프가 찍히고 스탬프가 찍힌  x 자리는 어느 문자가 오든 관계없는 자리가 된다. 따라서 0번째에 스탬프를 찍는다. 그럼 [2, 0]으로 도장이 찍히는데 역순으로 생각한 것이기 땜문에 [0, 2]가 정답이 된다.

[0, 2] 로 도장을 찍은 경우 _ _ _ _ _ -> a b c _ _ -> a b a b c 가 된다.

 

따라서 target에서 stamp에 해당하는 부분문자열의 시작 위치를 찾고 해당 위치에 도장을 찍는다. 도장을 다 찍었을 때 도장을 찍은 위치의 역순이 정답이 된다.

 

시간복잡도는 O(|target||stamp|)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/936.%20Stamping%20The%20Sequence.cpp